我知道这个问题不太具体。

我想要的只是有人告诉我如何将普通的归并排序转换为就地归并排序(或具有常量额外空间开销的归并排序)。

我所能找到的(在网上)都是说“这太复杂”或“超出了本文的范围”的页面。

唯一已知的就地合并(没有任何额外空间)的方法太复杂,无法简化为实用程序。(从这里拍摄)

即使它太复杂,如何使归并排序的基本概念是什么?


当前回答

关键的一步是让合并本身就位。这并不像那些来源说的那么难,但当你尝试的时候,你会失去一些东西。

看看合并的一个步骤:

[…list-sorted…| x列表…| y…发行b…]

我们知道这个排序的序列比其他的都小,x比A中的其他所有的都小,y也比b中的其他所有的都小。在x小于等于y的情况下,你只需要把指针移到A的起始点上。在y小于x的情况下,你必须将y洗牌过整个A来排序。最后一步是代价高昂的原因(退化情况除外)。

它通常更便宜(特别是当数组每个元素实际上只包含单个单词时,例如,一个指向字符串或结构的指针),用一些空间换取时间,并使用一个单独的临时数组来来回排序。

其他回答

这个答案有一个代码示例,实现了黄炳超和Michael a . Langston在论文《Practical in - place merge》中描述的算法。我不得不承认我不了解细节,但给定的合并步骤的复杂性是O(n)。

从实际的角度来看,有证据表明,纯就地实现在现实场景中并没有表现得更好。例如,c++标准定义了std::inplace_merge,顾名思义,这是一个就地合并操作。

假设c++库通常都得到了很好的优化,看看它是如何实现的是很有趣的:

1) libstdc++ (GCC代码库的一部分):std::inplace_merge

实现委托给__inplace_merge,通过尝试分配一个临时缓冲区来避免这个问题:

typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);

if (__buf.begin() == 0)
  std::__merge_without_buffer
    (__first, __middle, __last, __len1, __len2, __comp);
else
  std::__merge_adaptive
   (__first, __middle, __last, __len1, __len2, __buf.begin(),
     _DistanceType(__buf.size()), __comp);

否则,它将退回到一个实现(__merge_without_buffer),该实现不需要额外的内存,但不再在O(n)时间内运行。

2) libc++ (Clang代码库的一部分):std::inplace_merge

看起来相似。它委托给一个函数,该函数也尝试分配一个缓冲区。它将根据是否获得了足够的元素来选择实现。常量内存回退函数称为__buffered_inplace_merge。

也许回退仍然是O(n)时间,但关键是如果有临时内存可用,他们就不使用实现。


注意,c++标准通过将所需的复杂度从O(n)降低到O(nlog n),显式地给予实现选择这种方法的自由:

复杂性: 如果有足够的额外内存可用,则正好是N-1个比较。如果内存不足,则比较O(N log N)次。

当然,这并不能证明常数空间在O(n)时间内的合并永远不应该被使用。另一方面,如果它会更快,优化的c++库可能会切换到那种类型的实现。

这是我的C版本:

void mergesort(int *a, int len) {
  int temp, listsize, xsize;

  for (listsize = 1; listsize <= len; listsize*=2) {
    for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
      merge(& a[i], listsize, listsize);
    }
  }

  listsize /= 2;

  xsize = len % listsize;
  if (xsize > 1)
    mergesort(& a[len-xsize], xsize);

  merge(a, listsize, xsize);
}

void merge(int *a, int sizei, int sizej) {
  int temp;
  int ii = 0;
  int ji = sizei;
  int flength = sizei+sizej;

  for (int f = 0; f < (flength-1); f++) {
    if (sizei == 0 || sizej == 0)
      break;

    if (a[ii] < a[ji]) {
      ii++;
      sizei--;
    }
    else {
      temp = a[ji];

      for (int z = (ji-1); z >= ii; z--)
        a[z+1] = a[z];  
      ii++;

      a[f] = temp;

      ji++;
      sizej--;
    }
  }
}

它确实不容易或不有效,我建议您不要这样做,除非您真的必须这样做(您可能不必这样做,除非这是家庭作业,因为就地合并的应用程序主要是理论性的)。你不能用快速排序代替吗?无论如何,通过一些简单的优化,快速排序都会更快,而且它额外的内存是O(log N)。

不管怎样,如果你一定要做,那就必须做。这是我的发现:一和二。我不熟悉就地归并排序,但它的基本思想似乎是使用旋转来方便合并两个数组,而不使用额外的内存。

注意,这甚至比传统的归并排序还要慢。

关键的一步是让合并本身就位。这并不像那些来源说的那么难,但当你尝试的时候,你会失去一些东西。

看看合并的一个步骤:

[…list-sorted…| x列表…| y…发行b…]

我们知道这个排序的序列比其他的都小,x比A中的其他所有的都小,y也比b中的其他所有的都小。在x小于等于y的情况下,你只需要把指针移到A的起始点上。在y小于x的情况下,你必须将y洗牌过整个A来排序。最后一步是代价高昂的原因(退化情况除外)。

它通常更便宜(特别是当数组每个元素实际上只包含单个单词时,例如,一个指向字符串或结构的指针),用一些空间换取时间,并使用一个单独的临时数组来来回排序。

我知道我来晚了,但这是我昨天写的一个解决方案。我也在其他地方发布了这个帖子,但这似乎是SO上最受欢迎的就地合并帖子。我也没有在其他地方看到这个算法,所以希望这能帮助到一些人。

这个算法是最简单的形式,所以它可以被理解。它可以显著地调整以获得额外的速度。平均时间复杂度为:稳定的原地阵列归并为O(n.log₂n),整体排序为O(n.(log₂n)²)。

//                     Stable Merge In Place Sort
//
//
// The following code is written to illustrate the base algorithm. A good
// number of optimizations can be applied to boost its overall speed
// For all its simplicity, it does still perform somewhat decently.
// Average case time complexity appears to be: O(n.(log₂n)²)

#include <stddef.h>
#include <stdio.h>

#define swap(x, y)    (t=(x), (x)=(y), (y)=t)

// Both sorted sub-arrays must be adjacent in 'a'
// Assumes that both 'an' and 'bn' are always non-zero
// 'an' is the length of the first sorted section in 'a', referred to as A
// 'bn' is the length of the second sorted section in 'a', referred to as B
static void
merge_inplace(int A[], size_t an, size_t bn)
{
    int t, *B = &A[an];
    size_t  pa, pb;     // Swap partition pointers within A and B

    // Find the portion to swap.  We're looking for how much from the
    // start of B can swap with the end of A, such that every element
    // in A is less than or equal to any element in B.  This is quite
    // simple when both sub-arrays come at us pre-sorted
    for(pa = an, pb = 0; pa>0 && pb<bn && B[pb] < A[pa-1]; pa--, pb++);

    // Now swap last part of A with first part of B according to the
    // indicies we found
    for (size_t index=pa; index < an; index++)
        swap(A[index], B[index-pa]);

    // Now merge the two sub-array pairings.  We need to check that either array
    // didn't wholly swap out the other and cause the remaining portion to be zero
    if (pa>0 && (an-pa)>0)
        merge_inplace(A, pa, an-pa);

    if (pb>0 && (bn-pb)>0)
        merge_inplace(B, pb, bn-pb);
} // merge_inplace

// Implements a recursive merge-sort algorithm with an optional
// insertion sort for when the splits get too small.  'n' must
// ALWAYS be 2 or more.  It enforces this when calling itself
static void
merge_sort(int a[], size_t n)
{
    size_t  m = n/2;

    // Sort first and second halves only if the target 'n' will be > 1
    if (m > 1)
        merge_sort(a, m);

    if ((n-m)>1)
        merge_sort(a+m, n-m);

    // Now merge the two sorted sub-arrays together. We know that since
    // n > 1, then both m and n-m MUST be non-zero, and so we will never
    // violate the condition of not passing in zero length sub-arrays
    merge_inplace(a, m, n-m);
} // merge_sort

// Print an array */
static void
print_array(int a[], size_t size)
{
    if (size > 0) {
        printf("%d", a[0]);
        for (size_t i = 1; i < size; i++)
            printf(" %d", a[i]);
    }
    printf("\n");
} // print_array
 
// Test driver
int
main()
{
    int a[] = { 17, 3, 16, 5, 14, 8, 10, 7, 15, 1, 13, 4, 9, 12, 11, 6, 2 };
    size_t  n = sizeof(a) / sizeof(a[0]);
 
    merge_sort(a, n);
 
    print_array(a, n);

    return 0;
} // main