计数排序

1,计数排序是一个非基于比较的线性时间排序算法。
它对输入的数据有附加的限制条件：
(1)、输入的线性表的元素属于有限偏序集S；
(2)、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则 k=O(n)。
在这两个条件下，计数排序的复杂性为O(n)。
　　
2,计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

3，实例代码:

#include<iostream>
using namespace std;

//考虑重复元素的情况
void CountingSort(int data[], int n)
{
    int* tmp=new int[n];
    int max=data[0];
    for(int i=1;i<n;i++)
        max=(max>data[i]? max:data[i]);
    int* count = new int[max+1];
    memset(count, 0, (max+1)*sizeof(int));

    //统计每个元素的个数
    for (int i = 0; i < n; i++)
        count[data[i]]++;
    //数组中小于等于当前data[i]的元素个数
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--)
    {
        tmp[ count[data[i]]-1 ] = data[i];
        count[data[i]]--;
    }
    for (int i = 0; i < n; i++)
        data[i]=tmp[i];
    delete[] count;
    delete[] tmp;
}

void Output(int data[], int n)
{
    for(int i = 0 ; i < n ; i++ )
        cout << data[i] << " ";
    cout << endl;
}

int main()
{
    int data[]={73, 22, 93, 43, 55, 55, 14, 28, 65, 39, 81};
    int n=sizeof(data)/sizeof(data[0]);
    CountingSort(data,n);
    Output(data,n);
    return 0;
}