c++ - 无法使用计数排序获得正确的排序数组

Question

我目前正在研究计数排序算法。我设置了两个临时数组 C 和 B。 C是统计原数组中某个数出现的次数。然后它使用 C 中的元素将 A(原始数组)中的元素放置到 B 中的正确位置。我让我的 countingSort 函数在每次循环后打印出 C 以确保其中包含正确的值(确实如此，我正在用小样本量对其进行测试).当我在 C 的帮助下将 A 的元素插入到 B 时出现问题。

这是我的 countingSort 函数:

注意:我将一个包含 10 个整数的数组 2 0 3 2 5 4 3 6 10 传递给函数，临时数组 B，最大值 值(所以我知道 C 的大小)和数组 A

的大小

void countingSort(int A[], int B[], int k, int size){
    int C[k + 1];
    cout << "K: " << k << endl;

    for(int i = 0; i < k + 1; i++){
        C[i] = 0;
    }



    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }


    for(int i = 0; i < size; i++){
        C[A[i]] = C[A[i]] + 1;
    }

    cout << endl;


    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }


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


    cout << endl;
    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }



    for(int i = size + 1; i > 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }


    cout << endl;
    for(int i = 0; i < size; i++){
        cout << B[i] << " ";
    }


}

如您所见，我在每次循环后打印出 C，因此在第一个循环后它应该显示 C 是 0 0 0 0 0 0，它确实正确地打印出来了。在下一个 for 循环之后，C 应该是 2 1 2 2 1 1 1，它也可以正确打印出来。接下来它添加 C 的元素得到 2 3 5 7 8 9 10，它也被正确打印出来。现在，当我尝试将 A 的元素放入 B 时，我的问题就出现了。它应该打印 0 0 1 2 2 3 3 4 5 6，但它打印了 0 0 0 1 0 2 3 3 4 5。

我已经尝试在最后一个 for 循环中使用我的索引，但似乎无法弄清楚是什么导致 B 不正确。我该如何解决这个问题？我的总体目标是让计数排序适用于随机生成的大小为 40 且数字介于 1 到 25 之间的数组。

编辑:调用 countingSort 的主函数:

int sizeCount1 = 10;
int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0};

cout << "Counting Sort Version 1 (Pre Sort)" << endl;

for(int i = 0; i < sizeCount1; i++){
    cout << countOne[i] << " ";
}

cout << endl;


for(int i = 0; i < sizeCount1; i++){
    countTemp[i] = 0;
}



int max = 0;
for(int i = 0; i < sizeCount1; i++){
    if(countOne[i] > max){
        max = countOne[i];
    }
}

cout << "Max: " << max << endl;


countingSort(countOne, countTemp, max, sizeCount1);

cout << endl;

cout << "Counting Sort Version 1 (Post Sort)" << endl;


for(int i = 1; i < 10; i++){
    cout << countTemp[i] << " ";
}

cout << endl << endl;

Answer 1

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

否则你会得到未定义的行为。

同样在输出数组形成

for(int i = size-1; i >= 0; i--){
    B[C[A[i]]] = A[i];
    C[A[i]] = C[A[i]] - 1;
}

您的算法正确。现在只是试运行一下。这样您就可以在您的代码中找到这些类型的错误。

_{由于 OP 使用了 0-indexing。我在我的回答中使用了相同的内容}

_{如果你不能使用 vector ..使用new分配内存。为此检查一下引用资料。}

_{另一件事是，每当您编写计数排序代码时，总是要尝试证明您可以在辅助数组中保留范围。这很有帮助。}

计数排序代码:

void countingSort(int A[], int B[], int k, int size){
    int C[k + 1];
    for(int i = 0; i < k + 1; i++){
        C[i] = 0;
    }
    for(int i = 0; i < size; i++){
        C[A[i]] = C[A[i]] + 1;
    }
    for(int i = 0; i < k + 1; i++){
        C[i] = C[i] + C[i - 1];
    }
    for(int i = size-1; i >= 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }
}

主要代码

int sizeCount1 = 10;
int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0};

cout << "Counting Sort Version 1 (Pre Sort)" << endl;

for(int i = 0; i < sizeCount1; i++){
    countTemp[i] = 0;
}
int max = 0;
for(int i = 0; i < sizeCount1; i++){
    if(countOne[i] > max){
        max = countOne[i];
    }
}

cout << "Max: " << max << endl;


countingSort(countOne, countTemp, max, sizeCount1);
cout << "Counting Sort Version 1 (Post Sort)" << endl;
for(int i = 0; i < 10; i++){
    cout << countTemp[i] << " ";
}

cout << endl << endl;