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

starwing83

回复 52# pmerofc


    倒不尽然。比如说我的应用吧。

计时器。

计时器需要很频繁的插入删除，所以数据结构应该对插入删除友好，那么数组被pass。

计时器插入的时候是按序的，但删除的时候需要随机删，那么单链表被pass。

最后的实现手法是双链表，但是计时器是个队列，需要排序。

所以最终的结果就必须要做链表的排序了，而且是增量排序（插入的时候希望能自动排序）

其实用二叉树做这个需求应该是最好的，但是二叉树太过麻烦，时间和空间都不适宜（时间上讲，红黑树的处理比较复杂，而且主要并不是为了查询，红黑树最大的优势没有利用到；在大多数情况下，队列中元素较少（10个以内），因此用红黑树常数会很大；空间上讲，支持随机删除的红黑树至少要三个指针，比双链表结构大。）

需求看怎么有。需求再奇怪，一旦有了应用就不奇怪了。小乔真正没做对的地方是要提一下——这里只是为了教学，可能有点造作。

UPDATE：这么仔细一剖析，我发现实际上最好的结构好像是二叉最小堆………………sigh…………而且似乎用数组即可，这个……

群雄逐鹿中原

starwing83 发表于 2012-11-22 15:02
回复 52# pmerofc
最后的实现手法是双链表，但是计时器是个队列，需要排序。
所以最终的结果就必须要做链表的排序了，而且是增量排序（插入的时候希望能自动排序）

不用做链表排序，因为这个链表永远是排好序的。

问题：如何在一个排好序的链表中，找到位置，插入一个新的元素，并且保持排序完好。

starwing83

回复 55# 群雄逐鹿中原


    二分是没希望的。顺序查找呗。

hbmhalley

pmerofc 发表于 2012-11-22 14:39
回复 50# starwing83
我的意思是说，我不是说对链表不能用冒泡法，就如同不能说汽车并非不能用牛拉一样

愚蠢的到底是:

1. 对链表排序
2. 对链表用时间复杂度 Ω(n^2) 的算法排序
3. 对链表用冒泡算法排序

的哪个?

hbmhalley

pmerofc 发表于 2012-11-22 20:37
回复 57# hbmhalley
   冒泡算法排序

   因为需要大量的交换。

    你的意思是:

    1. 冒泡算法本身愚蠢, 因为需要大量交换
    2. 链表结点的交换操作很繁琐, 导致链表上的冒泡相比于数组上的性价比低
    3. 有同样作用于链表上的, 且所需操作比交换简洁, 且所有场景下所需时间优于冒泡的算法

    的哪个?