时间复杂度为O(n).
计数排序的基本思想就是对每一个输入元素X，确定出小于X的元素个数。
有了这一信息就可以把X直接放到它在最终输出数组中的位置上。
例如，如果有17个元素小于X，则X就属于第18个输出位置。
在计数排序算法的代码中，我们假定输入是个数组A[0...n-1]，length[A]=n。另外还需要两个数组：存放排序结果的B[0...n-1]，以及提供临时存储区的C[0...k].
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

void CountSort(int a[], int b[],int k,int num)
{
    int* c = new int[k+1];
    for (int i=0;i<=k;i++)
       c[i]=0;
    int size = num;
    for (int j=0;j<size;j++)
       c[a[j]]++;
    //c[i]包含等于i的元素个数
    for (i=1;i<=k;i++)
       c[i]=c[i]+c[i-1];
    //c[i]包含小于等于i的元素个数
    for (j=size-1;j>=0;j--)
    {
        b[c[a[j]]-1]=a[j];
        c[a[j]]--;
    }

        delete [] c;
}
void main()
{
    int num,max;
    cout<<"输入最大整数及输入个数"<<endl;
    cin>>max;
    cin>>num;
    int* a = new int[num];
    int* b = new int[num];
    cout<<"排序前："<<endl;
    for(int i=0;i<num;i++)
    {
        cin>>a[i];
        if (a[i]>max)
            i--;
    }
        
    CountSort(a,b,max,num);

    cout<<"排序后："<<endl;
    for (int j=0;j<num;j++)
    {
        cout<<b[j]<<endl;
    }

    delete [] a;
    delete [] b;
}