第一、任意一个比较排序算法在最好情况下的时间复杂度也是O(nlogN);

第二、计数排序

假设n个输入元素的每一个都是介于0到k之间的整数，计数排序可用，需要临时存储空间O(K),时间复杂度是O(n).

#include <iostream>
using namespace std;
void countingSort(int *A,int len,int max)
{
  if(A==NULL || len<=0)
  {
      return ;
  }
    int *count=new int[max+1];
    int i;
    for (i=0;i<max+1; i++)
    {
        count[i]=0;
    }
    for(i=0;i<len;i++)
    {
        count[A[i]]++;
    }
    int cur=0;
    for(i=0;i<=max;i++)
    {
        if (count[i]>0)
        {
            for(int j=0;j<count[i];j++)
            {
                A[cur++]=i;
            }
        }
    }
    delete [] count;
}
int main(int argc, const char * argv[])
{
    //int A[]={100,11,43,65};
    int A[]={56,3,5,68,100,32};
    //int A[]={68,100,32};
    countingSort(A, sizeof(A)/sizeof(int), 100);
    for(int i=0;i<sizeof(A)/sizeof(int);i++)
    {
        cout<<A[i]<<"   ";
    }
    cout <<endl;
    return 0;
}