请问：比“快速排序”效率高的算法是什么？

请问：比“快速排序”效率高的算法是什么？(不包括对快速排序的优化，比如：递归转循环，嵌入其他算法等)

解决方案 »

  1.   

    凡是通过比较来排序的算法时间复杂度不会比O（nlogn）再小了。所有同级别O(nlogn)的排序算法中，快排是最快的了。不通过比较的排序算法中，我知道的有:基数排序，时间复杂度大约为O(d*n),其中d表示关键字的个数,对于整数排序来说，d就是参与排序的整数的位数（比如2564的位数是4）。还有一位叫位图法排序的方法，时间复杂度为O（n）,但空间复杂度非常大。对整数排序来说，不管n有多大，所要的空间为2^32/8=512MByte.这种排序不能排重复元素。
      

  2.   

    是的，可以用决策树证明排序问题的下界是0(n*log n).