如何使用合并sortingalgorithm就地sorting?

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

我想要的是有人告诉我如何将正常的合并sorting转换为就地合并sorting(或具有恒定额外空间开销的合并sorting)。

我能find的所有网页都是“太复杂”或“超出本文范围”的页面。

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

即使它太复杂了, 如何进行合并sorting的基本概念是什么?

    克努特留下这个练习(第3卷,5.2.5)。 确实存在就地合并sorting。 必须认真执行。

    首先, 这里描述的天真就地合并不是正确的解决scheme。 它将性能降至O(N 2

    我们的想法是对数组的一部分进行sorting,而将其余部分用作合并工作区。

    例如下面的合并函数。

    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 ,两个sorting的子数组分别表示为范围[i, m)[j, n) 。 工作区域从w开始。 与大多数教科书中给出的标准合并algorithm相比,该algorithm交换了sorting后的子arrays和工作区之间的内容。 结果,前一个工作区域包含合并的已sorting元素,而存储在工作区域中的前一个元素则移至两个子数组。

    但是,有两个约束必须得到满足:

    1. 工作区域应该在数组的范围内。 换句话说,它应该足够大,以保持交换的元素,而不会造成任何过度的错误;
    2. 工作区可以与两个sorting的数组中的任何一个重叠,但是应该确保没有任何未合并的元素被覆盖;

    通过定义这种合并algorithm,很容易想象一个解决scheme,它可以sorting一半的数组; 接下来的问题是如何处理存储在工作区中的其余部分,如下所示:

     ... unsorted 1/2 array ... | ... sorted 1/2 array ... 

    一个直观的想法是recursionsorting工作区域的另一半,因此只有1/4个元素尚未被sorting。

     ... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ... 

    在这个阶段的关键点是,我们必须早晚sortingsorting后的1/4元素B和sorting的1/2元素A.

    工作区域是否只剩下1/4个元素,足以将A和B合并? 不幸的是,事实并非如此。

    但是,上面提到的第二个约束给了我们一个提示,我们可以利用它来安排工作区与任何一个子数组重叠,如果我们能够确保合并顺序的话,那些未合并的元素将不会被覆盖。

    实际上,我们可以不对工作区的后半部分进行sorting,而是对前半部分进行sorting,并将工作区放在两个sorting后的数组之间:

     ... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ... 

    这种设置效果将工作区域与子arraysA重叠。这个想法在[Jyrki Katajainen,Tomi Pasanen,Jukka Teuhola中提出。 “实用的in-place mergesort''。 北欧计算机学报,1996年]。

    所以唯一剩下的就是重复上述步骤,这样就减less了1/2,1/4,1/8 …的工作区域。当工作区域变得足够小的时候,例如只剩下两个元素,我们可以切换到一个简单的插入sorting来结束这个algorithm。

    这里是基于本文的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的地方。

    完整的源代码可以在这里find,详细的解释可以在这里find

    顺便说一句,这个版本不是最快的合并sorting,因为它需要更多的交换操作。 根据我的testing,它比标准版本更快,在每次recursion中都会分配额外的空间。 但是它比优化后的版本要慢,这个版本提前将原始数组加倍,并将其用于进一步合并。

    包括它的“大成果”,本文描述了几种就地合并sorting(PDF)的变体:

    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

    用较less的移动就地sorting

    Jyrki Katajainen,Tomi A. Pasanen

    它表明,可以使用O(1)额外空间,O(n log n / log log n)元素移动和n log 2 n + O(n log log n)比较来sortingn个元素的数组。 这是第一个在最坏情况下需要o(n log n)移动的就地sortingalgorithm,同时保证O(n log n)的比较,但是由于涉及常数因素,algorithm主要是理论上的兴趣。

    我认为这也是相关的。 我有一个躺在地上的打印输出,由一位同事传给我,但是我没有看到它。 它似乎涵盖了基本的理论,但是我对这个话题的认识还不够全面:

    http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

    最佳稳定合并

    安东尼奥斯Symvonis

    本文展示了如何稳定地将两个序列A和B分别与O(m + n)赋值O(mlog(n / m + 1))进行比较,并使用一个常量额外的空间量。 这个结果匹配所有已知的下限…

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

    看一下合并的一个步骤:

    [… list- sorted … | x … list- A … | y … list- B …]

    我们知道sorting后的序列比其他所有东西都less, x小于A中的其他所有元素, y小于B中的所有其他元素 。 在x小于或等于y的情况下,只需将指针移到A的开始位置即可。 在y小于x的情况下,必须将整个A sorting 。 最后一步是什么让这个昂贵(除了在退化的情况下)。

    它通常更便宜(特别是当数组实际上只包含每个元素的单个词,例如指向一个string或结构的指针)时间换取一些空间,并有一个单独的临时数组,您可以在它们之间来回sorting。

    这真的不容易或有效率,我build议你不要这样做,除非你真的必须这样做(并且你可能不必这样做,因为就地合并的应用大部分是理论上的,因此这是家庭作业)。 你不能使用quicksort吗? 无论如何,使用一些简单的优化,Quicksort将会更快,而其额外的内存是O(log N)

    无论如何,如果你必须这样做,那么你必须。 这是我发现的: 一个和两个 。 我不熟悉就地合并sorting,但似乎基本思想是使用旋转来促进两个数组合并,而不使用额外的内存。

    请注意,这比传统的合并sorting还要慢。

    仅供参考,这里是一个稳定的就地合并sorting的很好的实现 。 复杂,但不是太糟糕。

    我最终实现了一个稳定的就地合并sorting和一个稳定的Java 就地快速sorting 。 请注意复杂度是O(n(log n)^ 2)

    C中的无缓冲mergesort的一个例子

     #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 (@pb) if not found. */ { int i; for ( i = ba; 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 (@pb) if not found. */ { int i; for ( i = ba; 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, nh); ip_merge_(v, v+h, v+n); } } 

    自适应mergesort(优化)的一个例子。

    添加支持代码和修改,以便在任何大小的辅助缓冲区可用时加速合并(仍然可以在没有附加内存的情况下工作)。 使用前向和后向合并,循环旋转,小序列合并和sorting以及迭代合并。

     #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); } 

    这是我的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--; } } } 

    使用Kronrod的原始技术,就地合并sorting有一个相对简单的实现,但实现起来更简单。 一个说明这种技术的图例可以在这里find: http : //www.logiccoder.com/TheSortProblem/BestMergeInfo.htm 。

    也有与这个链接相关的作者更详细的理论分析的链接。

    我只是尝试使用插入sortingalgorithm在JAVA中合并sorting合并algorithm,使用以下步骤。
    1)有两个sorting的数组可用。
    2)比较每个数组的第一个值; 并将最小的值放入第一个数组中。
    3)使用插入sorting将较大的值放入第二个数组(从左到右)。
    4)然后再次比较第一个数组的第二个值和第二个数组的第一个值,并且做同样的事情。 但是当交换发生时,有一些线索可以比较其他项目,但只需要交换。

    我在这里做了一些优化。 在插入sorting中保持较less的比较。
    我发现这个解决scheme唯一的缺点是需要在第二个数组中更大的数组元素交换。

    例如)

    First___Array:3,7,8,9

    第二arrays:1,2,4,5

    然后,7,8,9使第二个数组每次交换(向左移动一个)其所有元素一个,使自己处于最后。

    所以这里的假设是交换项目比较两个项目可以忽略不计。

    https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

     package sorting; import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 }; mergeSort(array, 0, array.length -1); System.out.println(Arrays.toString(array)); int[] array1 = {4, 7, 2}; System.out.println(Arrays.toString(array1)); mergeSort(array1, 0, array1.length -1); System.out.println(Arrays.toString(array1)); System.out.println("\n\n"); int[] array2 = {4, 7, 9}; System.out.println(Arrays.toString(array2)); mergeSort(array2, 0, array2.length -1); System.out.println(Arrays.toString(array2)); System.out.println("\n\n"); int[] array3 = {4, 7, 5}; System.out.println(Arrays.toString(array3)); mergeSort(array3, 0, array3.length -1); System.out.println(Arrays.toString(array3)); System.out.println("\n\n"); int[] array4 = {7, 4, 2}; System.out.println(Arrays.toString(array4)); mergeSort(array4, 0, array4.length -1); System.out.println(Arrays.toString(array4)); System.out.println("\n\n"); int[] array5 = {7, 4, 9}; System.out.println(Arrays.toString(array5)); mergeSort(array5, 0, array5.length -1); System.out.println(Arrays.toString(array5)); System.out.println("\n\n"); int[] array6 = {7, 4, 5}; System.out.println(Arrays.toString(array6)); mergeSort(array6, 0, array6.length -1); System.out.println(Arrays.toString(array6)); System.out.println("\n\n"); //Handling array of size two int[] array7 = {7, 4}; System.out.println(Arrays.toString(array7)); mergeSort(array7, 0, array7.length -1); System.out.println(Arrays.toString(array7)); System.out.println("\n\n"); int input1[] = {1}; int input2[] = {4,2}; int input3[] = {6,2,9}; int input4[] = {6,-1,10,4,11,14,19,12,18}; System.out.println(Arrays.toString(input1)); mergeSort(input1, 0, input1.length-1); System.out.println(Arrays.toString(input1)); System.out.println("\n\n"); System.out.println(Arrays.toString(input2)); mergeSort(input2, 0, input2.length-1); System.out.println(Arrays.toString(input2)); System.out.println("\n\n"); System.out.println(Arrays.toString(input3)); mergeSort(input3, 0, input3.length-1); System.out.println(Arrays.toString(input3)); System.out.println("\n\n"); System.out.println(Arrays.toString(input4)); mergeSort(input4, 0, input4.length-1); System.out.println(Arrays.toString(input4)); System.out.println("\n\n"); } private static void mergeSort(int[] array, int p, int r) { //Both below mid finding is fine. int mid = (r - p)/2 + p; int mid1 = (r + p)/2; if(mid != mid1) { System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ " for p:"+p+" r:"+r); } if(p < r) { mergeSort(array, p, mid); mergeSort(array, mid+1, r); // merge(array, p, mid, r); inPlaceMerge(array, p, mid, r); } } //Regular merge private static void merge(int[] array, int p, int mid, int r) { int lengthOfLeftArray = mid - p + 1; // This is important to add +1. int lengthOfRightArray = r - mid; int[] left = new int[lengthOfLeftArray]; int[] right = new int[lengthOfRightArray]; for(int i = p, j = 0; i <= mid; ){ left[j++] = array[i++]; } for(int i = mid + 1, j = 0; i <= r; ){ right[j++] = array[i++]; } int i = 0, j = 0; for(; i < left.length && j < right.length; ) { if(left[i] < right[j]){ array[p++] = left[i++]; } else { array[p++] = right[j++]; } } while(j < right.length){ array[p++] = right[j++]; } while(i < left.length){ array[p++] = left[i++]; } } //InPlaceMerge no extra array private static void inPlaceMerge(int[] array, int p, int mid, int r) { int secondArrayStart = mid+1; int prevPlaced = mid+1; int q = mid+1; while(p < mid+1 && q <= r){ boolean swapped = false; if(array[p] > array[q]) { swap(array, p, q); swapped = true; } if(q != secondArrayStart && array[p] > array[secondArrayStart]) { swap(array, p, secondArrayStart); swapped = true; } //Check swapped value is in right place of second sorted array if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) { prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced); } p++; if(q < r) { //q+1 <= r) { q++; } } } private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) { int i = secondArrayStart; for(; i < array.length; i++) { //Simply swap till the prevPlaced position if(secondArrayStart < prevPlaced) { swap(array, secondArrayStart, secondArrayStart+1); secondArrayStart++; continue; } if(array[i] < array[secondArrayStart]) { swap(array, i, secondArrayStart); secondArrayStart++; } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){ break; } } return secondArrayStart; } private static void swap(int[] array, int m, int n){ int temp = array[m]; array[m] = array[n]; array[n] = temp; } } 

    Swift中mergesort的一个例子。

     func mergeAndSort (array: Array<UInt32>) -> Array<UInt32> { let halfIndex = array.count / 2 let leftArray = Array(array[0..<halfIndex]) let rightArray = Array(array[halfIndex..<array.count]) let sortedLeftArray = (leftArray.count == 1) ? leftArray : mergeAndSort(leftArray) var sortedRightArray = (rightArray.count == 1) ? rightArray : mergeAndSort(rightArray) var sortedArray: Array<UInt32> = [] var rightI = 0 var leftI = 0 while(leftI < sortedLeftArray.count) { if sortedLeftArray[leftI] < sortedRightArray[rightI] { sortedArray.append(sortedLeftArray[leftI]) leftI++ } else { sortedArray.append(sortedRightArray[rightI]) rightI++ } if leftI == sortedLeftArray.count { for i in rightI..<sortedRightArray.count { sortedArray.append(sortedRightArray[i]) } } if rightI == sortedRightArray.count { for i in leftI..<sortedLeftArray.count { sortedArray.append(sortedLeftArray[i]) } break } } return sortedArray } var unsortedArray: Array<UInt32> = [] for i in 0...22 { let randomNumber = arc4random_uniform(100) unsortedArray.append(randomNumber) } var sortedArray = mergeAndSort(unsortedArray)