合并排序错误c++

Question

我是 C++ 的新手，之前只用 python 编码，但 python 现在对我来说太慢了。我在 python 中做了一个合并排序算法并且它起作用了。但是现在我将它翻译成 C++，并且在我的 IDE 中出现了一堆错误。我的错误是什么？

#include <iostream>

using namespace std;

int *sort(int lenght, int lis[]) {
    int units = lenght;
    int umt;
    int tiles = 1;
    while (units > 1) {
        bool whole = true;
        umt = units % 2;
        if (umt = 1) {
            units++;
            whole = false;
        }
        units = units / 2;
        tiles = tiles * 2;
        if (whole) {
            int buffd[units];
            int add_l = 0;
            int add_r = 0;
            int prod_l = 0;
            int prod_r = prod_l + tiles / 2;
            for (int k = 0; k < units; k++) {
                int buffd[units];
                int add_l = 0;
                int add_r = 0;
                int prod_l = k * tiles;
                int prod_r = prod_l + tiles / 2;
                for (int f = 0; f < tiles; f++) {
                    if (lis[prod_l + add_l] <= lis[prod_r + add_r]) {
                        buffd[f] = lis[prod_l + add_l];
                        add_l++;
                        if (add_l = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_r + add_r + e];
                            }
                            f = tiles;
                        }
                    } else {
                        buffd[f] = lis[prod_r + add_r];
                        add_r++;
                        if (add_r = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_l + add_l + e];
                            }
                            f = tiles;
                        }
                    }
                }
                for (int i = prod_l; i < prod_l + tiles; i++) {
                    lis[i] = buffd[i - prod_l];
                }
            }
        } else {
            int buffd[units];
            int add_l = 0;
            int add_r = 0;
            int prod_l = 0;
            int prod_r = prod_l + tiles / 2;
            for (int k = 0; k < units - 1; k++) {
                int buffd[units];
                int add_l = 0;
                int add_r = 0;
                int prod_l = k * tiles;
                int prod_r = prod_l + tiles / 2;
                for (int f = 0; f < tiles; f++) {
                    if (lis[prod_l + add_l] <= lis[prod_r + add_r]) {
                        buffd[f] = lis[prod_l + add_l];
                        add_l++;
                        if (add_l = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_r + add_r + e];
                            }
                            f = tiles;
                        }
                    } else {
                        buffd[f] = lis[prod_r + add_r];
                        add_r++;
                        if (add_r = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_l + add_l + e];
                            }
                            f = tiles;
                        }
                    }
                }
            }
            for (int i = prod_l; i < prod_l + tiles; i++) {
                lis[i] = buffd[i - prod_l];
            }
        }
    }
    return lis;
}

int main() {
    int to_sort[8] = { 23, 1, 654, 2, 4, 87, 3, 1 };
    cout << "sortiert: ";
    int *sorted;
    sorted = sort(8, to_sort);
    for (int p = 0; p < 8; p++) {
        cout << sorted[p] << " ";
    }
    return 0;
}

错误是德文的，我不知道为什么，IDE 的其余部分是英文的。有谁知道如何将其设置为英语，我正在使用 JetBrains 的 Clion。

Answer 1

您的代码中存在一些主要问题：

比较必须使用==而不是=，这是赋值运算符。
我应该删除 buffd、add_l、add_r、prod_l 和 prod_r 的冗余定义。
许多 C++ 编译器不支持可变长度数组定义，例如 int buffd[units]。这些是与 C90 可选功能兼容的扩展，可能导致大型数组 堆栈溢出 。您应该分配这些数组或使用 std::vector.
这些局部数组声明的大小不正确：应该是 int buffd[tiles];，而不是 int buffd[units]。随之而来的是未定义的行为。
最后一个 for 循环在前一个循环的主体之外，这是不正确的。
当 add_l 或 add_r 等于 tiles / 2.

f

你的非递归算法在一般情况下无法成功，我让它适用于长度为 2 的幂的数组，令人惊讶的是它可能来自你的翻译 python版本。在 python 和 C++ 中编程 mergesort 的方法要简单得多。

经过一些额外的工作，我简化了您的代码并使其适用于一般情况：

#include <iostream>

using namespace std;

int *sort(int length, int lis[]) {
    for (int tile = 1; tile < length; tile += tile) {
        int tiles = tile + tile;
        int *buffd = new int[tiles];
        for (int prod_l = 0; prod_l < length; prod_l += tiles) {
            int add_l = 0;
            int max_l = tile;
            int add_r = 0;
            int max_r = tile;
            int prod_r = prod_l + max_l;
            int f = 0;
            if (prod_r >= length)
                break;
            if (prod_r + max_r > length)
                max_r = length - prod_r;
            for (;;) {
                if (lis[prod_l + add_l] <= lis[prod_r + add_r]) {
                    buffd[f++] = lis[prod_l + add_l++];
                    if (add_l == max_l) {
                        while (add_r < max_r) {
                            buffd[f++] = lis[prod_r + add_r++];
                        }
                        break;
                    }
                } else {
                    buffd[f++] = lis[prod_r + add_r++];
                    if (add_r == max_r) {
                        while (add_l < max_l) {
                            buffd[f++] = lis[prod_l + add_l++];
                        }
                        break;
                    }
                }
            }
            for (int i = 0; i < f; i++) {
                lis[prod_l + i] = buffd[i];
            }
        }
        delete[] buffd;
    }
    return lis;
}

int main() {
    int to_sort[8] = { 23, 1, 654, 2, 4, 87, 3, 1 };
    for (int i = 1; i < 8; i++) {
        cout << "sortiert: ";
        int *sorted = sort(i, to_sort);
        for (int p = 0; p < i; p++) {
            cout << sorted[p] << " ";
        }
        cout << endl;
    }
    return 0;
}

这里有一个经典的自上而下的递归实现供参考：

void mergesort(int lis[], int lo, int hi, int *tmp) {
    if (hi - lo >= 2) {
        int mid = (hi - lo) / 2;
        mergesort(lis, lo, lo + mid, tmp);
        mergesort(lis, lo + mid, hi, tmp);
        for (int i = 0; i < mid; i++)
            tmp[i] = lis[lo + i];
        for (int i = 0, j = lo + mid, k = lo; i < mid;) {
            if (j >= hi || tmp[i] <= lis[j])
                lis[k++] = tmp[i++];
            else
                lis[k++] = lis[j++];
        }
    }
}

int *mergesort(int length, int lis[]) {
    int *tmp = new int[length / 2];
    mergesort(lis, 0, length, tmp);
    delete[] tmp;
    return lis;
}

合并排序错误c++

Merge sort errors c++

c++

mergesort