算法导论 - 线性时间排序 - 计数排序

老王

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k＝O(n)时，排序的运行时间为\Theta(n)。

计数排序的基本思想是：对每一个输入元素x，计算小于x的元素个数，利用这一信息，就可以直接把x放到它在输出数组中的合适位置上。例如，如果有17个元素小于x，则x就应该在第18个输出位置上，当有几个元素相同时，这一方案要略做修改，因为不能把它们放在同一个输出位置上。

在计数排序算法的代码中，假设输入是一个数组A[1…n]，A.length = n；我们还需要两个数组：B[1…n]用于存放排序的输出，C[0…k]用于提供临时存储空间。

[C++] 纯文本查看 复制代码

//#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

// 计数排序
void CountingSort(int arrIntA[], int arrIntB[], size_t k, size_t nLength)
{
    // 临时存储空间（0～k区间）
    int* pArrIntC = malloc(sizeof(int) * (k + 1));
    memset(pArrIntC, 0, sizeof(int) * (k + 1));

    // 数组A中各个值为i的元素的个数存放于数组C中
    for (size_t i = 0; i <= nLength; i++)
        pArrIntC[arrIntA[i]]++;

    // 数组C中C[i]元素的值为小于等于数值i的个数
    for (size_t i = 1; i <= k; i++)
        pArrIntC[i] += pArrIntC[i - 1];

    // 排序
    for (intptr_t i = nLength; i >= 0; i--)
    {
        arrIntB[pArrIntC[arrIntA[i]] - 1] = arrIntA[i];
        pArrIntC[arrIntA[i]]--;
    }

    free(pArrIntC);
}

int main()
{
    // 输入数组A
    int arrIntA[] = { 5, 4, 3, 2, 1, 10, 9, 8, 7, 6/*, -1, -2, -3, -4, -5*/ };
    size_t nCount = sizeof(arrIntA) / sizeof(arrIntA[0]);
    // 输出数组B
    int* pArrIntB = malloc(sizeof(arrIntA));
    memset(pArrIntB, 0, sizeof(arrIntA));

    CountingSort(arrIntA, pArrIntB, 10, nCount - 1);

    for (size_t i = 0; i < nCount; i++)
        printf("%d\n", pArrIntB[i]);

    return 0;
}

计数排序的一个重要性质就是它是稳定的，具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序相同。也就是说，对两个相同的数来说，在输入数组中先出现的数，在输出数组中也位于前面。通常，这种稳定性只有当进行排序的数据还附带卫星数据时才比较重要。计数排序的稳定性很重要的另一个原因是：计数排序经常会被用作基数排序算法的一个子过程。