原来除了快速排序等O(nlogn)优秀排序外,竟然还存在着计数排序、基数(radix)排序、和桶排序等线性O(n)排序算法。
尽管它们的实现前提是某种特定情况,而且速度上不一定快过快排等O(nlogn)之流。但它们的设计思路值得一提。传统排序算法都是基于比较大小而诞生的。而它们却抛开了这点,迎来了突破。这就是所谓的Thinking
out of the box!!!
其实早有科学家证明过基于比较的排序算法的极限就是O(nlogn),这无疑是给这种思路的继续发展判了死刑。这种思路上的否定值得借鉴。
ps.具体的算法实现可参看《算法导论》排序一章。
基数排序套用计数排序可以很好地应用于高精度中的排序。