使用c++进行计数排序

Question

#include<iostream>
#include <fstream>
#include <algorithm>
using namespace std;

void countsort(int a[], int b[], int n, int k, int& count) {
    int *c = new int[k + 1];

    for (int i = 0; i <= k; i++) {
        count = count + 1;
        c[i] = 0;
    }
    for (int j = 0; j < n; j++) {
        count = count + 1;
        c[a[j]]++;
    }
    
    
    for (int i = 1; i <= k; i++) {
        count = count + 1;
        c[i] = c[i] + c[i - 1];
    }
    int x;
    for (int j = n - 1; j >= 0; j--) {
        count = count + 1;
        x=c[a[j]]-1;
        b[x] = a[j];
        c[a[j]]--;
    }
    
    delete[] c;
}

int main() {
    ifstream fin;
    int n;
    int* a;
    int* b;
    string fname;
    int count = 0;

    cout << "enter file name" << endl;
    cin >> fname;
    cout << "enter arr size" << endl;
    cin >> n;
    fname += ".txt";
    fin.open(fname);
    a = b = new int[n];
    for (int i = 0; i < n; i++) {
        fin >> a[i];
    }
    fin.close();
    // unsorted array
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    int k = *max_element(a, a + n);
    cout<<endl<<k<<endl;

    countsort(a, b, n, k, count);

    // Output sorted array
    for (int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
    cout << endl;

    cout << "Number of operations: " << count << endl;

    delete[] a;
    delete[] b;

    return 0;
}

数组 b 中的输出是错误的，我不知道我犯了什么错误

输入

3
4
3
2
0
2
0
0
0
2

输出 2 2 2 2 2 2 2 0 0 2

ai网站找不到问题，我还尝试在代码之间打印数组以查看输出出错的地方，我认为 这个区域有错误

for (int i = 1; i <= k; i++) {
        count = count + 1;
        c[i] = c[i] + c[i - 1];
    }

    for (int j = n - 1; j >= 0; j--) {
        count = count + 1;
        x=c[a[j]]-1;
        b[x] = a[j];
        c[a[j]]--;
    }
 

我得到的完整输出是

输入文件名 输入_csort_1 输入数组大小 10 3 4 3 2 0 2 0 0 0 2 4 2 2 2 2 2 2 2 0 0 2 操作次数：29

Answer 1

你的程序有几个问题，但你最大的问题是你的代码过于复杂且结构不好。

首先，尝试将算法分解为其基本步骤：初始化计数数组，从输入数组填充计数，从计数填充输出数组。继续进一步分解这些步骤，直到您非常清楚每个步骤需要做什么。例如，填充输出数组可能需要为计数数组中的每个条目写入多个输出。确保您了解如何做到这一点。如果对您有帮助，请在纸上记下笔记。 在第一阶段，您不需要编写代码。这是为了在你的头脑中清楚地了解你正在尝试做什么。

接下来，您想要单独解决每个小问题。编写一小段代码来初始化计数数组。代码应该足够小，以便您知道编写的每一行发生了什么，以及每个变量的值应该是什么。现在您的函数中显然不是这种情况，例如，您无缘无故地不断增加 count 变量，并不断混淆

n

和

k

的含义。保持代码足够小，以免以这种方式感到困惑，并以易于记住它们的作用的方式选择变量名称。一旦你写完一段代码，你应该立即单独测试它。如果它的行为不符合预期，您只需修复一小部分代码，这比修复复杂的算法容易得多。

单独解决每个步骤并首先对其进行测试。乍一看，这似乎会减慢您的速度，但事实并非如此。它使事情变得易于管理和整洁。

一旦您确定已正确实现所有各个步骤，您就可以将其组合到更大的算法中。如果某些内容不起作用，请确保跟踪失败的步骤，并再次单独测试该步骤以查找失败的输入。

冲洗并重复，直到获得有效的程序。快乐编码！