把殷版的《数据结构》内部排序部分大致看了一遍,还是感觉到了收获。由于对基数排序(不是一个路数)和归并排序(额外n的存储空间,很致命)并不是很感兴趣,所以就没学习这两个部分。另外,外部排序还没开始,下一步即将开始。
大体的感想是:
1,排序的思想和代码实现都有谱了。以前,一说到qsort,要写代码,难受死了,非常费劲,但这次看完之后感觉非常明白,甚至能够把代码背下来。想面我的,不怕了。
2,快速排序确实是无可匹敌的。但是就像任何事情一样,都不是万能的。明白了,快速排序原来也需要和其他的方法一起合作才能通吃(详见"排序学习笔记(2) - 快速排序")。
3,堆排序也很牛。我曾经问别人堆排序使用的是什么结构,95%以上的人都说是树或者链表;呵呵,让我感觉自己很有面子。
4,下面的表说明了都有哪种情况的事情可以由哪个排序来处理。
5,最后,最重要的,我觉得处理几乎所有的问题时候,技术都不是最重要的,即使当技术很重要的时候,也要讲求80/20原则。就是说,在工期、资源方面实现一个很难的算法可能比较不现实,所以就可以选择一个比较简单的,比如shell排序。排序是整个工程中性能的瓶颈吗?感觉可能是,但是实际上恐怕未必;把其他的地方优化一下,可能就OK了。在退一万步,如果我们用c++的话,stl里面的qsort()简直就是那一根稻草,凭啥不去抓?而是自己去重新建一个不圆不扁的轮子?(跑题了,技术跑到了管理中)
技术方面的总结就不做了,下面的这位兄弟做的非常全面,感谢先:
http://blog.csdn.net/myjava_024/archive/2008/11/04/3220319.aspx
这里把他总结的表格超过来:
排序法 |
平均时间 |
最差情形 |
稳定度 |
额外空间 |
备注 |
冒泡 |
O(n2) |
O(n2) |
稳定 |
O(1) |
n小时较好 |
交换 |
O(n2) |
O(n2) |
不稳定 |
O(1) |
n小时较好 |
选择 |
O(n2) |
O(n2) |
不稳定 |
O(1) |
n小时较好 |
插入 |
O(n2) |
O(n2) |
稳定 |
O(1) |
大部分已排序时较好 |
基数 |
O(logRB) |
O(logRB) |
稳定 |
O(n) |
B是真数(0-9),R是基数(个十百) |
Shell |
O(nlogn) |
O(ns) 1<s<2 |
不稳定 |
O(1) |
s是所选分组 |
快速 |
O(nlogn) |
O(n2) |
不稳定 |
O(nlogn) |
n大时较好 |
归并 |
O(nlogn) |
O(nlogn) |
稳定 |
O(1) |
n大时较好 |
堆 |
O(nlogn) |
O(nlogn) |
不稳定 |
O(1) |
n大时较好 |