合并排序实现不起作用

Question

我试图使用数组里用C实现归并排序，这里是我的代码：

#include <stdio.h> 
#include <stdlib.h> 

void merge(int s[], int low, int middle, int high) 
{ 
    int i,l=0,r=0; 
    int left[high/2], right[high/2]; 

    for(i = low; i<=middle; i++) left[i-low] = s[i]; 
    for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i]; 

    i = low; 
    while(l <= middle-low || r <= high - middle - 1) 
    { 
     if(left[l] <= right[r]) 
     { 
      s[i++] = left[l]; 
      l++; 
     } 
     else 
     { 
      s[i++] = right[r]; 
      r++; 
     } 
    } 
    while(l <= middle-low) 
    { 
     s[i++] = left[l]; 
     l++; 
    } 
    while(r <= high - middle - 1) 
    { 
     s[i++] = left[r]; 
     r++; 
    } 
} 

void mergesort(int s[], int low, int high) 
{ 
    int i; 
    int middle; 
    if(low < high){ 
     middle = (low + high)/2; 
     mergesort(s, low, middle); 
     mergesort(s, middle+1, high); 
     merge(s, low, middle, high); 
    } 
} 

int main() 
{ 
    int nums[] = {5, 345, 1, 120, 40, 3450}; 
    int size = (sizeof(nums))/(sizeof(int)); 
    int i; 
    for(i = 0; i < size; i++) 
     printf("%d ", nums[i]); 
    printf("\n"); 
    mergesort(nums, 0, size); 
    for(i = 0; i < size; i++) 
     printf("%d ", nums[i]); 
    printf("\n"); 
    return 0; 
} 

输出：

5 345 1 120 40 3450 
0 1 4 5 40 120 

这是一种接近。有人能指出我的错误吗？谢谢。

Answer 1

你在几个地方访问数组越界。您的代码使用C风格范围，其中包含下限L和专有上限H。独占意味着上限H不是（子）数组中的有效索引。

for (i = L; i < U; i++) ... 

或

i = L; 
while (i < U) ... 

一个大于或 - 等于运营商<=在这样的循环应该让你警惕，因为应suprious添加或减法：在范围看起来像一个典型的循环1.在某些情况下它们可能是正确的，但它们通常是不稳定的数组索引的后果。

让我们修改与C风格的范围你的代码记：

int left[high/2], right[high/2]; 

的数组的大小是错误的。左边的数组有middle - low个元素，右边的数组有high - middle个元素。如果数组大小为high - low是奇数，则右侧的元素多于左侧。

for(i = low; i<=middle; i++) left[i-low] = s[i]; 

你错误地把中间元素放在左边的数组中。它是正确数组的第一个元素。

for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i]; 

同样在这里，加上你访问s[high]这是一个超出数组。

i = low; 
while(l <= middle-low || r <= high - middle - 1) 

应具备的条件和<没有-1。更重要的是，这两个条件都应该是真实的，否则你会进入超出边界的子阵列;因此运营商应该是'& &`。

if(left[l] <= right[r]) 

该<=是好的，但只有一次。

while(l <= middle-low) 
{ 
    s[i++] = left[l]; 
    l++; 
} 
while(r <= high - middle - 1) 
{ 
    s[i++] = left[r]; 
    r++; 
} 

在这里，它应该是<了。还请注意，您访问left的索引r，这可能只是复制和粘贴的错字。

if(low < high){ 
    middle = (low + high)/2; 
    mergesort(s, low, middle); 
    mergesort(s, middle+1, high); 
    merge(s, low, middle, high); 
} 

这里，megesort第二个电话应该是middle，不middle + 1。因为上限是独占的而下限不是，所以相邻的数组共享相同的界限。

这里有一个排序的作品：

void merge(int s[], int low, int middle, int high) 
{ 
    int i, l = 0, r = 0; 
    int left[middle - low]; 
    int right[high - middle]; 

    for (i = low; i < middle; i++) left[i - low] = s[i]; 
    for (i = middle; i < high; i++) right[i - middle] = s[i]; 

    i = low; 
    while (low + l < middle && middle + r < high) { 
     if (left[l] < right[r]) { 
      s[i++] = left[l]; 
      l++; 
     } else { 
      s[i++] = right[r]; 
      r++; 
     } 
    } 

    while (low + l < middle) { 
     s[i++] = left[l]; 
     l++; 
    } 

    while (middle + r < high) { 
     s[i++] = right[r]; 
     r++; 
    } 
} 

void mergesort(int s[], int low, int high) 
{ 
    int middle; 

    if (low + 1 < high) { 
     middle = (low + high)/2; 
     mergesort(s, low, middle); 
     mergesort(s, middle, high); 
     merge(s, low, middle, high); 
    } 
} 

的代码能够进一步提高。左侧和右侧子阵列的不同索引使维护和测试代码变得困难。如果您已经了解了指针算术，那么您可以完全通过将array + low和大小作为新的数组基地进行绑定来完成绑定，因为EOF在评论中已经提出了建议。

Answer 2

M Oehm在他的回答中提供了原始代码的解释和固定示例。

这是一个替代版本，它执行临时数组的一次分配，并使用一对共递归函数来避免数据的复制。我不确定为什么经常使用自顶向下合并排序，自底向上合并排序是非递归的，速度更快一些，而且更易于理解。

在我的系统上，Intel 2600K 3.4ghz，这个例子可以在大约2秒内对2000万个32位整数进行排序。 （自底向上合并排序大约需要1.9秒）。

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee); 
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee); 
void MergeRuns(int a[], int b[], size_t ll, size_t rr, size_t ee); 

void TopDownMergeSort(int a[], size_t n) 
{ 
    int *b; 
    if(n < 2)       // if size < 2 return 
     return; 
    b = malloc(n * sizeof(int));  // one time allocation 
    TopDownSplitMergeAtoA(a, b, 0, n); 
    free(b); 
    return; 
} 

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee) 
{ 
size_t rr; 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    rr = (ll + ee)>>1;     // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    MergeRuns(b, a, ll, rr, ee);  // merge b to a 
} 

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee) 
{ 
size_t rr; 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    rr = (ll + ee)>>1;     // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    MergeRuns(a, b, ll, rr, ee);  // merge a to b 
} 

void MergeRuns(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;      // b[]  index 
    size_t l = ll;      // a[] left index 
    size_t r = rr;      // a[] right index 
    while(1){       // merge data 
     if(a[l] <= a[r]){    // if a[l] <= a[r] 
      b[o++] = a[l++];   // copy a[l] 
      if(l < rr)     // if not end of left run 
       continue;    //  continue (back to while) 
      while(r < ee)    // else copy rest of right run 
       b[o++] = a[r++]; 
      break;      //  and return 
     } else {      // else a[l] > a[r] 
      b[o++] = a[r++];   // copy a[r] 
      if(r < ee)     // if not end of right run 
       continue;    //  continue (back to while) 
      while(l < rr)    // else copy rest of left run 
       b[o++] = a[l++]; 
      break;      //  and return 
     } 
    } 
}