给定大量数字时，基数排序无法正确排序

Question

我必须为我的作业实现二进制基数排序。虽然我已经让它工作了，但一旦它遇到大量数字（通常是 300+），它就会停止正确排序（实际上并没有对它们进行排序）。有谁知道问题出在哪里？

vector<unsigned char> A; //gets input from file that we have been given, containing 1000 numbers
vector<unsigned char> C(2);
vector<unsigned char> B(A.size());

for (int i = 0; i < A.size(); i++) {
    B.push_back(0);
}

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

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

    C[1] += C[0];

    for (int j = A.size() - 1; j >= 0; j--) {
        B[--C[(int)(A[j] >> k) & 1]] = (int)A[j];
    }

    std::swap(A, B);
}

经过一番测试，似乎限制为256个号码。所以当它超过 256 个数字时，算法就不能再对它进行排序了

Answer 1

查看声明和用法

vector<unsigned char> C(2);
B[--C[(int)(A[j] >> k) & 1]]

任何元素 C[i] 包含 0 到 255 之间的 N。因此索引 --C[(int)(A[j] >> k) & 1] 总是小于 255。

解决方案：

vector<size_t> C(2);

给定大量数字时，基数排序无法正确排序

Radix sort not sorting properly when given lots of numbers

c++

algorithm

sorting

radix-sort