计数排序中的整理过程是否有必要？

Question

我发现标准的计数排序最后都有一个整理的过程，通过反复地查找使排序结果填回原数组。
在我看来这似乎有点太麻烦了，直接依次回填不就可以了吗？请教各位大大，你们怎么看？

void counting_sort(int lst[], int length) {
    /*
     * 功能：计数排序；注：计数排序要求排序的数据为自然数，且相对稠密。
     * 参数：lst：待排序的数组，length：数组的长度
     * 返回值：无
     */

    // 找出数组内的最大值
    int max = lst[0];
    for (int i = 0; i < length; i++) if (lst[i] > max) max = lst[i];

    // 申请最大值长度的空间并初始化
    int *tmp = new int[max + 1];
    for (int i = 0; i <= max; i++) tmp[i] = 0;

    // 计数
    for (int i = 0; i < length; i++) tmp[lst[i]]++;

    // 将计数的结果回填
    do while (tmp[max]--) lst[--length] = max;
    while (max--);

    // 删除申请的堆空间
    delete[]tmp;
}

Answer 1

关于计数排序，我觉得你的算法好像少了一个步骤，参考这篇博客，似乎缺少了累加这个步骤。

算法本身不去讨论，单从临时数组和结果数组的大小来看：

计数排序本身是一种特性空间换时间的做法，所以注意到 int *tmp = new int[max + 1]，这里按最大数申请了一个巨大的临时空间。这个临时空间的大小和原数组的大小有可能是不等的（你拿不连续的整数试试就明白了），但结果大小和原数组大小肯定相同，那这里必然会出现一个回填过程。