合并排序实现不起作用

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。 Exclusive 表示上限 H 不是（子）数组中的有效索引。范围内的典型循环如下所示：

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

或

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

此类循环中的大于或等于运算符 <= 应该让您保持警惕，对 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++;
}

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

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 和大小作为新数组基数来完成 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
        }
    }
}

合并排序实现不起作用

Merge-sort implementation doesn't work

c

arrays

sorting

mergesort