我知道这个问题不太具体。
我想要的只是有人告诉我如何将普通的归并排序转换为就地归并排序(或具有常量额外空间开销的归并排序)。
我所能找到的(在网上)都是说“这太复杂”或“超出了本文的范围”的页面。
唯一已知的就地合并(没有任何额外空间)的方法太复杂,无法简化为实用程序。(从这里拍摄)
即使它太复杂,如何使归并排序的基本概念是什么?
我知道这个问题不太具体。
我想要的只是有人告诉我如何将普通的归并排序转换为就地归并排序(或具有常量额外空间开销的归并排序)。
我所能找到的(在网上)都是说“这太复杂”或“超出了本文的范围”的页面。
唯一已知的就地合并(没有任何额外空间)的方法太复杂,无法简化为实用程序。(从这里拍摄)
即使它太复杂,如何使归并排序的基本概念是什么?
当前回答
这个答案有一个代码示例,实现了黄炳超和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++库可能会切换到那种类型的实现。
其他回答
这个答案有一个代码示例,实现了黄炳超和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++库可能会切换到那种类型的实现。
我知道我来晚了,但这是我昨天写的一个解决方案。我也在其他地方发布了这个帖子,但这似乎是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
包括它的“大结果”,本文描述了就地归并排序的几个变体(PDF):
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf
少移动的就地排序
于尔基·卡塔贾宁、托米·
证明了n 元素可以使用O(1)进行排序 额外空间,O(n log n / log log n) 元素移动,nlog2n + O(nlog Log n)比较。这是第一次 需要就地排序算法 O (nlogn)在最坏情况下移动 同时保证O(n log n) 比较,不过由于不变 所涉及的因素是算法 主要是理论兴趣。
我认为这也是相关的。我有一份打印本,是同事传给我的,但我还没读过。它似乎涵盖了基本理论,但我对这个主题不够熟悉,无法判断它有多全面:
http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681
最优稳定合并
安东尼奥斯·西姆沃尼斯
本文介绍了如何稳定地进行归并 两个序列A和B,大小为m和 n, m≤n,分别为O(m+n) 作业,O (mlog (n / m + 1)) 比较和只使用一个常数 额外空间的数量。这 结果匹配所有已知的下界…
它确实不容易或不有效,我建议您不要这样做,除非您真的必须这样做(您可能不必这样做,除非这是家庭作业,因为就地合并的应用程序主要是理论性的)。你不能用快速排序代替吗?无论如何,通过一些简单的优化,快速排序都会更快,而且它额外的内存是O(log N)。
不管怎样,如果你一定要做,那就必须做。这是我的发现:一和二。我不熟悉就地归并排序,但它的基本思想似乎是使用旋转来方便合并两个数组,而不使用额外的内存。
注意,这甚至比传统的归并排序还要慢。
Knuth将此作为练习(Vol 3, 5.2.5)。确实存在就地归并排序。它们必须谨慎执行。
首先,这里描述的简单的就地合并并不是正确的解决方案。它将性能降低到O(N2)。
其思想是对数组的一部分进行排序,而将其余部分用作合并的工作区域。
例如下面的合并函数。
void wmerge(Key* xs, int i, int m, int j, int n, int w) {
while (i < m && j < n)
swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
while (i < m)
swap(xs, w++, i++);
while (j < n)
swap(xs, w++, j++);
}
取数组xs,两个排序的子数组分别表示为范围[i, m)和[j, n)。工作区域从w开始,与大多数教科书给出的标准合并算法相比,该算法在排序子数组和工作区域之间交换内容。结果,前一个工作区域包含合并的排序元素,而存储在工作区域中的前一个元素被移动到两个子数组中。
但是,有两个约束条件是必须满足的:
工作区域应该在数组的边界内。换句话说,它应该足够大,以容纳交换进来的元素,而不会引起任何越界错误。 工作区域可以与两个排序数组中的任何一个重叠;但是,它必须确保没有任何未合并的元素被覆盖。
定义了这个合并算法后,很容易想象出一个解决方案,它可以对数组的一半进行排序;接下来的问题是,如何处理剩余的未排序部分存储在工作区域,如下图所示:
... unsorted 1/2 array ... | ... sorted 1/2 array ...
一个直观的想法是对工作区域的另一半进行递归排序,这样就只有1/4的元素还没有排序。
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
这一阶段的关键点是我们必须归并已排序的1/4元素B 对1/2个元素A进行排序。
剩下的工作区域(只包含1/4个元素)是否大到足以合并 A和B?不幸的是,事实并非如此。
然而,上面提到的第二个约束给了我们一个提示,如果我们能确保合并序列中未合并的元素不会被覆盖,我们可以通过安排工作区域与任何一个子数组重叠来利用它。
实际上,我们不需要对工作区域的后半部分进行排序,而是可以对前半部分进行排序,并将工作区域放在两个排序数组之间,就像这样:
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
这种设置有效地安排了工作区域与子阵列a的重叠 在Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola中提出。“实用的就地归并排序”。计算机学报,1996]。
所以剩下的唯一事情就是重复上面的步骤,这将工作区域从1/2,1/4,1/8,…当工作区域变得足够小(例如,只剩下两个元素),我们可以切换到普通的插入排序来结束这个算法。
下面是基于本文在ANSI C语言中的实现。
void imsort(Key* xs, int l, int u);
void swap(Key* xs, int i, int j) {
Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}
/*
* sort xs[l, u), and put result to working area w.
* constraint, len(w) == u - l
*/
void wsort(Key* xs, int l, int u, int w) {
int m;
if (u - l > 1) {
m = l + (u - l) / 2;
imsort(xs, l, m);
imsort(xs, m, u);
wmerge(xs, l, m, m, u, w);
}
else
while (l < u)
swap(xs, l++, w++);
}
void imsort(Key* xs, int l, int u) {
int m, n, w;
if (u - l > 1) {
m = l + (u - l) / 2;
w = l + u - m;
wsort(xs, l, m, w); /* the last half contains sorted elements */
while (w - l > 2) {
n = w;
w = l + (n - l + 1) / 2;
wsort(xs, w, n, l); /* the first half of the previous working area contains sorted elements */
wmerge(xs, l, l + n - w, n, u, w);
}
for (n = w; n > l; --n) /*switch to insertion sort*/
for (m = n; m < u && xs[m] < xs[m-1]; ++m)
swap(xs, m, m - 1);
}
}
其中wmerge是前面定义的。
完整的源代码可以在这里找到,详细的解释可以在这里找到
顺便说一下,这个版本并不是最快的归并排序,因为它需要更多的交换操作。根据我的测试,它比标准版本更快,标准版本在每次递归中分配额外的空间。但它比优化版本慢,优化版本提前将原始数组翻倍,并将其用于进一步合并。