3

我正在尝试实现合并排序，但我无法让它工作。如果有人能找到并指出我的想法（和代码）中的错误，我将不胜感激。
没有不必要代码的主要功能：

int main(int argc, char *argv[]) {
    int n = 0;
    std::cin >> n;
    int num[n];

    for(int i = 0; i < n; i++) {
        std::cin >> num[i];
    }

    sort(num, &num[n - 1], n);

    return(0);
}

合并排序功能：

int *sort(int *s, int *e, int size) {
    if(s == e) {
        return(s);
    }

    int mid = (size + 1) / 2;

    //split array recursively to 1-element arrays

    int *left  = sort(s, (s + mid - 1), mid);
    int *right = sort(s + mid, e, size - mid);

    int *counter = s;

    //merge arrays back together

    while(left < (s + mid - 1) && right <= e) {
        //std::cout << *left << " " << *right << std::endl;

        for(; left < (s + mid - 1) && *left <= *right; left++, counter++) {
            *counter = *left;
        }

        for(; right <= e && *right <= *left; right++, counter++) {
            *counter = *right;
        }
    }

    for(; left < (s + mid - 1); left++, counter++) {
        *counter = *left;
    }
    for(; right <= e; right++, counter++) {
        *counter = *right;
    }

    return(s);
}

输入0 ：
5
4 3 2 1 0输出0
：
0 0 0 0 0

输入1：
5
0 1 2 3 4
输出1：
1 2 4 4 4

输入 2：
2
0 1
输出 2：
1 1

4

2 回答 2

2

看起来您正在将一个值复制到另一个值而不保存原始值（并对其进行处理）：

*counter = *left;
于 2012-04-24T19:24:16.690 回答
2

您的问题似乎出在*counter = *leftand *counter = *right。该算法的通常实现使用单独的数组来创建新的合并数组。但在这种情况下，您正在合并它inplace。当您这样做时*counter = *left，该值会丢失，这可能会导致您在示例运行中看到的所有零。

合并时，可以通过两种方式进行。创建一个临时数组并继续写入它而不是*counter在耗尽两个数组的所有元素后用临时数组重新填充实际数组，或者在要合并的数组大小小于时诉诸插入排序一个预定义的值。

这两种方法都在 http://en.literateprograms.org/Merge_sort_%28C%29中详细给出

PS：我也认为您应该将条件更改left < (s + mid - 1)为left <=(s + mid -1)在所有地方。

于 2012-04-24T20:11:05.813 回答