時(shí)間復(fù)雜度為O(n).
計(jì)數(shù)排序的基本思想就是對(duì)每一個(gè)輸入元素X，確定出小于X的元素個(gè)數(shù)。
有了這一信息就可以把X直接放到它在最終輸出數(shù)組中的位置上。
例如，如果有17個(gè)元素小于X，則X就屬于第18個(gè)輸出位置。
在計(jì)數(shù)排序算法的代碼中，我們假定輸入是個(gè)數(shù)組A[0...n-1]，length[A]=n。另外還需要兩個(gè)數(shù)組：存放排序結(jié)果的B[0...n-1]，以及提供臨時(shí)存儲(chǔ)區(qū)的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的元素個(gè)數(shù)
    for (i=1;i<=k;i++)
       c[i]=c[i]+c[i-1];
    //c[i]包含小于等于i的元素個(gè)數(shù)
    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<<"輸入最大整數(shù)及輸入個(gè)數(shù)"<<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;
}