我认为用冒泡法对链表进行排序很蠢，元芳，这事儿你怎么看？

群雄逐鹿中原

回复 41# pmerofc

元方，我坚持认为是。

一下能多冒几个泡，干嘛要一个一个冒泡。从这个角度讲，冒泡算法是有点愚蠢。
   

asdmonster

pmerofc 发表于 2012-11-19 17:49
回复 6# liuiang

怎么个容易法?上代码.

KanonInD

pmerofc 发表于 2012-11-19 15:53
我确实想这样说的
因为如果需要一个有序的链表
开始建立链表时就可以实现

修改版归并排序效果不错。
http://stackoverflow.com/questio ... lementation-so-fast

耗资喜欢猫

sonicling 发表于 2012-11-19 20:37
回复 15# pmerofc

敢问，{9,8,7,6,5,4,3,2,1}，这样的你插入排序时间是多少？，是不是应该是1+2+...n,对于这样的数列，高一的数学知识就可以秒杀，然后再用Big-O notation，去掉低阶项，敢问，这值是多少？

starwing83

回复 7# pmerofc


    不容易，反而一个完整链表容易排序。链表是天生适合归并排序的，数组反而不适合（需要分配新空间）。

通常如果不得不有建链表排序的需求，要么用索引，如果速度要求不是特别高，就只有插入排序了。

冒泡，对于基本有序的数组或者链表都是有用的，但是还是不如插入排序。

基于比较的高级排序中，平均性能最好的是快排，其次是桶堆排，然后是希尔，归并排最后，因为要分配新空间。
而基本排序中，最快的就是快排了，冒泡和选择其实都不太理想。（我初二刚学排序的时候，还以为选择是世界上最快的排序法呢= =）

而链表又不太一样，链表最快的排序方法应该是归并，平均性能和最坏性能都很好。然后应该就是快排了，而桶堆排和希尔是不可能的。链表实现归并和快排都比数组方便。但是这是基于对整个链表排序的，如果是建表排序高级方法基本上就都没辙了。

基本排序里面，插入排序是最自然的。冒泡和选择的性能不了解，但是至少有一点，就是不够自然。

如果实在是对性能要求高，可以考虑用桶排，Linux内核就是这么实现计时器的。

最近做一个计时器的时候遇到了这个问题，但是因为这个计时器主要是短时触发，桶排没有很大的优势，所以采用的是插入排序。一次遍历找位置，然后直接插入，不算CPU cache的话，反而比数组的插入排序更优（需要不断移动位置）。

UPDATE：把堆排和桶排搞混了，我这脑子= =

starwing83

回复 49# pmerofc


    何意？