c - 合并排序实现不起作用

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) ...

大于等于运算符 <= in such loops should be make you wary, as should surprised additions or subtraction of 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);
    }
}

代码还有待改进。左右子数组的不同索引使得代码难以维护和测试。如果你已经学过指针算法，你可以不用 low。通过传递完全绑定(bind) array + low以及作为新数组基础的大小，正如 EOF 在评论中所建议的那样。