计数排序给出错误的结果

Question

计数排序总是给出不正确的结果，总是以 0 开头并缺少最后一个数字，即给定输入 9、8、7、6、5，它会给出 0、5、6、7、8。

我的逻辑：

使用 C 作为数字 0-9 的桶
通过 C[A[i]] = C[A[i]] + 1
遍历 C 中的所有存储桶并将所有项目加起来 <= 当前存储桶以找到 A[i]
将 C 中的项目复制到输出数组 B，记住每次复制时减少 C 中的桶

// 顺便说一句，之前用来问问题的代码相同，但这是一个不同的问题

#include <iostream>
#define MAX 10

int main(void){

    int A[MAX] = {9, 3, 9, 3, 9, 3, 0, 0, 9, 3};
    int C[10];
    int B[MAX] = {0};

    for (int i = 0; i < 10; i++)    C[i] = 0;

    std::cout << "\nOriginal array = ";
    for (int i = 0; i < MAX; i++)   std::cout << " " << A[i] << " ";
    std::cout << "\n";

    //  increment count of buckets containing this digit accordingly
    for (int i = 0; i < MAX; i++)   C[A[i]] =  C[A[i]] + 1;

    //  count all count <= the current bucket to determine the correct index
    for (int i = 1; i < 10; i++)    C[i] = C[i] + C[i-1];

    //  copy array elements to output array B and decrement C array accordingly
    for (int i = MAX-1; i >= 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]]-1;
    }

    std::cout << "\nSorted array = ";
    for (int i = 0; i < MAX; i++)  std::cout << " " << B[i] << " ";
    std::cout << "\n";

    return 0;
}

结果总是错误的，第一个元素是前导 0，并且总是缺少最后一个元素。

Answer 1

正如 Jarod42 所说，您的问题是 C 中的数组从索引 [0] 开始，因此您得到的答案数组 B 的索引不正确。简单修复：

//  copy array elements to output array B and decrement C array accordingly
for (int i = MAX - 1; i >= 0; i--) {
//  B[C[A[i]]] = A[i];     // Wrong
    B[C[A[i]] - 1] = A[i]; // Right
    C[A[i]] = C[A[i]] - 1;
}

计数排序给出错误的结果

counting sort gives wrong results

c++

sorting

counting