时间戳

首页 > 解决方案 > 合并排序错误 C++

c++ - 合并排序错误 C++

问题描述

我对 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。

标签： c++mergesort

解决方案

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

  • 比较必须使用==而不是=，它是赋值运算符。
  • buffd, add_l,add_r和应该删除prod_l的冗余定义。prod_r
  • int buffd[units]许多 C++ 编译器不支持可变长度数组定义。这些是与 C90 可选功能兼容的扩展，可能会导致大型数组的堆栈溢出。您应该分配这些数组或使用std::vector.
  • 这些本地数组声明的大小不正确：应该是int buffd[tiles];，而不是int buffd[units]。未定义的行为随之而来。
  • 最后一个for循环在前一个循环的主体之外，这是不正确的。
  • 当or 或equals时，您不会f在从另一个切片复制剩余元素之前递增。add_ladd_rtiles / 2
  • 您的非递归算法在一般情况下无法成功，我让它适用于 2 的幂的数组长度，令人惊讶的是它可能来自您的 python 版本的翻译。mergesort在 python 和 C++ 中有更简单的编程方法。

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

#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;
}

推荐阅读