c++ - 优化计数排序？

Question

假设输入是从 0 到 N 的 N 个数字(有重复项)，我如何针对小型和大型数组优化以下代码:

void countingsort(int* input, int array_size)
{
    int max_element = array_size;//because no number will be > N

    int *CountArr = new int[max_element+1]();

    for (int i = 0; i < array_size; i++)
        CountArr[input[i]]++;

    for (int j = 0, outputindex = 0; j <= max_element; j++)
        while (CountArr[j]--)
            input[outputindex++] = j;

    delete []CountArr;
}

不需要稳定的排序。

编辑:如果还不清楚，我说的是优化算法。

Answer 1

恕我直言，这里没有任何问题。当 max_element 很小、排序的数字非稀疏(即连续且没有间隙)并且大于或等于零时，我强烈推荐这种方法。

一个小调整，我将替换 new/delete 并仅使用堆声明一个有限数组，例如最大元素为 256。

int CountArr[256] = { }; // Declare and initialize with zeroes

当你改变这些规则时，即稀疏的负数，你会很难适应这种方法。您需要找到一个最佳的哈希函数来将数字重新映射到高效的数组。散列变得越复杂，与成熟的排序算法相比的优势就会减少。