我知道这个问题不太具体。
我想要的只是有人告诉我如何将普通的归并排序转换为就地归并排序(或具有常量额外空间开销的归并排序)。
我所能找到的(在网上)都是说“这太复杂”或“超出了本文的范围”的页面。
唯一已知的就地合并(没有任何额外空间)的方法太复杂，无法简化为实用程序。(从这里拍摄)
即使它太复杂，如何使归并排序的基本概念是什么?
当前回答
这是我的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--;
}
}
}
其他回答
这是我的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--;
}
}
}
关键的一步是让合并本身就位。这并不像那些来源说的那么难，但当你尝试的时候，你会失去一些东西。
看看合并的一个步骤:
[…list-sorted…| x列表…| y…发行b…]
我们知道这个排序的序列比其他的都小，x比A中的其他所有的都小，y也比b中的其他所有的都小。在x小于等于y的情况下，你只需要把指针移到A的起始点上。在y小于x的情况下，你必须将y洗牌过整个A来排序。最后一步是代价高昂的原因(退化情况除外)。
它通常更便宜(特别是当数组每个元素实际上只包含单个单词时，例如，一个指向字符串或结构的指针)，用一些空间换取时间，并使用一个单独的临时数组来来回排序。
C语言中无缓冲区归并排序的一个例子。
#define SWAP(type, a, b) \
do { type t=(a);(a)=(b);(b)=t; } while (0)
static void reverse_(int* a, int* b)
{
for ( --b; a < b; a++, b-- )
SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
if (a != b && b != c)
{
reverse_(a, b);
reverse_(b, c);
reverse_(a, c);
}
return a + (c - b);
}
static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
* sequence (@p b) if not found. */
{
int i;
for ( i = b-a; i != 0; i /= 2 )
{
int* mid = a + i/2;
if (*mid < key)
a = mid + 1, i--;
}
return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
* sequence (@p b) if not found. */
{
int i;
for ( i = b-a; i != 0; i /= 2 )
{
int* mid = a + i/2;
if (*mid <= key)
a = mid + 1, i--;
}
return a;
}
static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
int n1 = b - a;
int n2 = c - b;
if (n1 == 0 || n2 == 0)
return;
if (n1 == 1 && n2 == 1)
{
if (*b < *a)
SWAP(int, *a, *b);
}
else
{
int* p, * q;
if (n1 <= n2)
p = upper_bound_(a, b, *(q = b+n2/2));
else
q = lower_bound_(b, c, *(p = a+n1/2));
b = rotate_(p, b, q);
ip_merge_(a, p, b);
ip_merge_(b, q, c);
}
}
void mergesort(int* v, int n)
{
if (n > 1)
{
int h = n/2;
mergesort(v, h); mergesort(v+h, n-h);
ip_merge_(v, v+h, v+n);
}
}
一个自适应归并排序的例子(优化)。
添加支持代码和修改，以在任何大小的辅助缓冲区可用时加速合并(在没有额外内存的情况下仍然可以工作)。使用前向和后向合并、环旋转、小序列合并和排序以及迭代合并排序。
#include <stdlib.h>
#include <string.h>
static int* copy_(const int* a, const int* b, int* out)
{
int count = b - a;
if (a != out)
memcpy(out, a, count*sizeof(int));
return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
int count = b - a;
if (b != out)
memmove(out - count, a, count*sizeof(int));
return out - count;
}
static int* merge_(const int* a1, const int* b1, const int* a2,
const int* b2, int* out)
{
while ( a1 != b1 && a2 != b2 )
*out++ = (*a1 <= *a2) ? *a1++ : *a2++;
return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
const int* a2, const int* b2, int* out)
{
while ( a1 != b1 && a2 != b2 )
*--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}
static unsigned int gcd_(unsigned int m, unsigned int n)
{
while ( n != 0 )
{
unsigned int t = m % n;
m = n;
n = t;
}
return m;
}
static void rotate_inner_(const int length, const int stride,
int* first, int* last)
{
int* p, * next = first, x = *first;
while ( 1 )
{
p = next;
if ((next += stride) >= last)
next -= length;
if (next == first)
break;
*p = *next;
}
*p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
if (a != b && b != c)
{
int n1 = c - a;
int n2 = b - a;
int* i = a;
int* j = a + gcd_(n1, n2);
for ( ; i != j; i++ )
rotate_inner_(n1, n2, i, c);
}
return a + (c - b);
}
static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
* @note faster for small sequences. */
{
while ( a != b && b != c )
if (*a <= *b)
a++;
else
{
int* p = b+1;
while ( p != c && *p < *a )
p++;
rotate_(a, b, p);
b = p;
}
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
* @note works with or without additional memory. */
{
int n1 = b - a;
int n2 = c - b;
if (n1 <= n2 && n1 <= ts)
{
merge_(t, copy_(a, b, t), b, c, a);
}
else if (n2 <= ts)
{
merge_backward_(a, b, t, copy_(b, c, t), c);
}
/* merge without buffer. */
else if (n1 + n2 < 48)
{
ip_merge_small_(a, b, c);
}
else
{
int* p, * q;
if (n1 <= n2)
p = upper_bound_(a, b, *(q = b+n2/2));
else
q = lower_bound_(b, c, *(p = a+n1/2));
b = rotate_(p, b, q);
ip_merge_(a, p, b, t, ts);
ip_merge_(b, q, c, t, ts);
}
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
const int ts)
{
int* p = a + cs*2;
for ( ; p <= b; a = p, p += cs*2 )
ip_merge_(a, a+cs, p, t, ts);
if (a+cs < b)
ip_merge_(a, a+cs, b, t, ts);
}
static void smallsort_(int* a, int* b)
/* insertion sort.
* @note any stable sort with low setup cost will do. */
{
int* p, * q;
for ( p = a+1; p < b; p++ )
{
int x = *p;
for ( q = p; a < q && x < *(q-1); q-- )
*q = *(q-1);
*q = x;
}
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
int* p = a + cs;
for ( ; p <= b; a = p, p += cs )
smallsort_(a, p);
smallsort_(a, b);
}
static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
int cs = 16;
smallsort_chunk_(cs, v, v+n);
for ( ; cs < n; cs *= 2 )
ip_merge_chunk_(cs, v, v+n, t, ts);
}
static void* get_buffer_(int size, int* final)
{
void* p = NULL;
while ( size != 0 && (p = malloc(size)) == NULL )
size /= 2;
*final = size;
return p;
}
void mergesort(int* v, int n)
{
/* @note buffer size may be in the range [0,(n+1)/2]. */
int request = (n+1)/2 * sizeof(int);
int actual;
int* t = (int*) get_buffer_(request, &actual);
/* @note allocation failure okay. */
int tsize = actual / sizeof(int);
mergesort_lower_(v, n, t, tsize);
free(t);
}
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是前面定义的。
完整的源代码可以在这里找到，详细的解释可以在这里找到
顺便说一下，这个版本并不是最快的归并排序，因为它需要更多的交换操作。根据我的测试，它比标准版本更快，标准版本在每次递归中分配额外的空间。但它比优化版本慢，优化版本提前将原始数组翻倍，并将其用于进一步合并。
包括它的“大结果”，本文描述了就地归并排序的几个变体(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)) 比较和只使用一个常数 额外空间的数量。这 结果匹配所有已知的下界…
