计数排序

计数排序是一个类似于桶排序的排序算法，其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C，C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由 Harold H. Seward 提出。

计数排序是一种算法复杂度 O(n) 的排序方法，适合于小范围集合的排序。

比如100万学生参加高考，我们想对这100万学生的数学成绩（假设分数为0到100）做个排序。我们如何设计一个最高效的排序算法。本文不光给出计数排序算法的传统写法，还将一步步深入讨论算法的优化，直到时间复杂度和空间复杂度最优。

计数排序假设n个输入元素中的每一个都是介于0-k的整数，此处k为某个整数。当k等于O（n）时，计数排序的运行时间为Θ（n）。

计数排序顾名思义离不开计数，我们要计的是输入元素中相同元素出现的次数。对每一个输入元素x，确定小于x的元素的个数，那样排序之后，x在最终输出数组中的位置就可以确定了。

例如：如果有17个元素小于x，则x就位于第18个输出的位置上。当然有几个元素相同时，这个方法就略微改进一下，因为不能将它们放在同一个位置上。

它的基本思想是对每一个输入元素x,输入小于x的元素个数，利用这一信息，可以直接把x放到它在输出数组中的位置上。在计数排序算法的代码中，假设输入是一个数组A[1…n],A.length=n,还需要两个数组，B[1…n]存放排序的输出，C[0…k]提供临时存储空间。

计数排序的伪代码如下：

COUNT—SORT(A,B,k)

let C[0..k]be a new array

for i=0 to k

         C[i]=0

for j=1 to A.length

         C[A[j]]=C[A[j]]+1

//C[i]now contains the number of elements equal to i

for i=1 to k

         C[i]=C[i]+C[i-1]

//C[i] now contains the number of elements less than or equal to i

for j=A.length downto 1

B[C[A[j]]]=A[j]

C[A[j]]=C[A[j]]-1

这个就是这个算法的典型解法，我把它作为方案1.

这个算法的实际扫描次数为 n+k （不包括写的次数）

方案一：

public static void Sort(int[] A, out int[] B, int k)
{
    Debug.Assert(k > 0);
    Debug.Assert(A != null);
    int[] C = new int[k + 1];
    B = new int[A.Length];
    for (int j = 0; j < A.Length; j++)
    {
        C[A[j]]++;
    }
    for (int i = 1; i <= k; i++)
    {
        C[i] += C[i-1];
    }
    for (int j = A.Length - 1; j >= 0; j--)
    {

        B[C[A[j]]-1] = A[j];
        C[A[j]]--;
    }
}

上面代码是方案1 的解法，也是计数排序算法的经典解法，麻省的教材上也是这样解。不过这个解法并不是最优的，因为空间复杂度还应该可以优化，我们完全可以不要那个输出的数组B，直接对A进行排序。在继续看方案2之前，我建议大家先自己思考一下，看看是否有办法省略掉数组B。

方案2

我们对上述代码进行优化

public static void Sort(int[] A, int k)
{
    Debug.Assert(k > 0);
    Debug.Assert(A != null);
    int[] C = new int[k + 1];
    for (int j = 0; j < A.Length; j++)
    {
        C[A[j]]++;
    }
    int z = 0;
    //由于C数组下标 i 就是A 的值，所以我们不需要保留A中原来的数了，这个代码减少了一个数组B，而且要比原来的代码简化了很多。
    for (int i = 0; i <= k; i++)
    {
        while (C[i]-- > 0)
        {//0的个数是2个，则A前两位为0；
         //1的个数是1个，则A第三位为1；以此类推。

            A[z++] = i;
        }
    }
}

完整的代码：

/*********************************
           计数排序
**********************************/
#include <iostream>

using namespace std;


void G_CountingSort(int *A,int *B,int len,int k)
{
    if (A == NULL || k <= 0 || len <= 0)
        return;

    int *C = new int[k + 1];
    //int C[k + 1];

    int i, j;
    //初始化
    for (i = 0; i <= k; ++i)
        C[i] = 0;

    //统计值为A[i]的个数,C[i]是等于i的元素个数
    for (j = 0; j < len; ++j)
        C[A[j]]++;

    //确定值A[i]在最终输出数组B中位置,C[i]是小于等于i的元素个数
    for (i = 1; i <= k; ++i)   //注意这里的i值要从1开始
        C[i] += C[i - 1];

    for (j = len - 1; j >= 0; j--)
    {

        B[C[A[j]] - 1] = A[j];
        C[A[j]]--;
    }

}


//空间复杂度优化部分，可省略上面两个for循环;
//由于C数组下标 i 就是A[j]的值，所以我们
//不需要保留A中原来的数了，这个代码减少了一个数组B，而且要比原来的代码简化了很多。
void Y_CountingSort(int *A, int len, int k)
{
    if (A == NULL || k <= 0 || len <= 0)
        return;

    int *C = new int[k + 1];
    //int C[k + 1];

    int i, j;
    //初始化
    for (i = 0; i <= k; ++i)
        C[i] = 0;

    //统计值为A[i]的个数,C[i]是等于i的元素个数
    for (j = 0; j < len; ++j)
        C[A[j]]++;


    int z = 0;

    //0的个数是2个，则A前两位为0；
    //1的个数是1个，则A第三位为1；以此类推。

    for (i = 0; i <= k; i++)
        while (C[i]-- > 0)
            A[z++] = i;

}





int main()
{
    int A[8] = { 2, 5, 3, 0, 2, 3, 0, 3 };
    int B[8];

    G_CountingSort(A, B, 8, 5);
    Y_CountingSort(A, 8, 5);

    //显示优化的计数排序结果
    cout << "优化：";
    for (int i = 0; i < 8; i++)
        cout << A[i] << " ";
    cout << endl;

    //显示普通的计数排序结果
    cout << "普通：";
    for (int i = 0; i < 8; i++)
        cout << B[i] << " ";
    cout << endl;


    system("pause");
    return 0;
}

时间复杂度分析

时间复杂度是多少呢？第1~2行for循环所花时间为Θ（k）。第3~4行for循环所花时间为Θ（n）。
第6~7行for循环所花时间为Θ（k）。第9~11行for循环所花时间为Θ（n）。这样总的时间就是Θ（k+n）。在实践中，档k =
O（n）时，我们常采用计数排序，这时运行时间为Θ（n）。

特点

提前必须是已知待排序的关键字为整型且范围已知。

时间复杂度为O(n+k)，不是基于比较的排序算法，因此效率非常之高。

稳定性好，这个是计数排序非常重要的特性，可以用在后面介绍的基数排序中。

但需要一些辅助数组，如C[0..k]，因此待排序的关键字范围0~k不宜过大。