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

Question

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

的帮助下将 A 的元素插入 B 时出现问题

这是我的 countingSort 函数：

注意：我将一个包含 10 个整数的数组 2 0 3 2 5 4 3 6 10 传递给函数，临时数组 B，maximum 值（所以我知道 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。我在我的回答中使用了相同的}

_{如果您不能使用向量..使用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;

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

Not getting correct sorted array with a counting sort

c++

sorting

counting-sort

计数排序代码：

主要代码