任何比较排序在最好情况下都要经过Ω(nlgn)，即比较排序的下界为Ω(nlgn)。

合并排序和堆排序都是渐进最优的。

要突破Ω(nlgn)，就要进行非比较排序。计数排序、基数排序和桶排序都有非比较的一些操作来确定排序顺序，它们可以达到线性运行时间。

 

计数排序法:

计数排序的基本思想是对每一个输入元素x,确定出小于x的元素个数。有了这个信息就可以把x直接放到他在最终输出数组中的位置上。

计数排序适用于小范围集合的排序。它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 但是当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。

代码如下：

#include 
     
      #include 
      
       //输入 A，输出Bvoid count_sort(int A[], int B[], int nLen) {  //1.找出待排序的数组中最大和最小的元素  int k = INT_MIN;  for (int i = 0; i < nLen; i++) {    if (A[i] > k) {      k = A[i];    }  }  //===============  int *C = new int [k];//统计的暂存数组  //初始化C  for (int i = 0; i < k; i ++) {    C[i] = 0;  }  //2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项  //统计j的次数  for (int j = 0; j < k; j++){    C[A[j]] = C[A[j]] + 1;//统计A[j]出现了多少次  }  //3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）  for (int i = 0; i < k; i++) {    C[i] = C[i] + C[i-1];//对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数  }  //4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个 元素就将C(i)减去1  //逆向遍历源数组（保证稳定性），根据计数数组中对应的值填充到先的数组中  for (int j = nLen; j>=0; j++) {    B[C[A[j]]] = A[j];    C[A[j]] = C[A[j]] -1;  }  delete[] C;}int main(){  int a[] = {
   5,9,3,9,10,9,2,4,13,10};  const size_t sz = sizeof(a)/sizeof(a[0]);  for (int i = 0; i < sz;  i++ ) {    std::cout << a[i] << " ";  }}
      
     

 

基数排序：

基数排序是首先按最低有效位数字进行排序的，它从低位到高位进行排序。它是一种稳定性的算法。