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

hbmhalley

pmerofc 发表于 2012-11-22 21:03
冒泡法本身虽然效率不高
但在数组中应用我觉得不算愚蠢
因为数组的插入操作很啰嗦
但对于链表来说
容易插入是其优势
交换则是其劣势
避其长处而用其短处——而且是极其频繁的使用
显然不是明智之举
但若想坐实“所有场景下所需时间优于冒泡的算法”这个结论
恐怕也不那么容易
如果你有反例
我很愿意洗耳恭听

    >> 交换则是其劣势
    是交换相邻元素. 同样是三行, 说不上劣势吧

    >> 但若想坐实“所有场景下所需时间优于冒泡的算法”这个结论
    >> 恐怕也不那么容易
    >> 如果你有反例
    >> 我很愿意洗耳恭听
    见 8L 与 35L.

hbmhalley

pmerofc 发表于 2012-11-22 21:46
Ω(n^2) 量级的交换
不是小数目

我觉得用不用冒泡同样可以做得很好，甚至可能更好。
    如果给出具体的数据，我们可以走一遍

>>Ω(n^2) 量级的交换
>>不是小数目

so? 插入排序不也是n^2的么
还是你想说冒泡比插入大了个 3 的常数? 那因为选择排序的存在, 数组上的冒泡岂不也没必要存在

>>我觉得用不用冒泡同样可以做得很好，甚至可能更好。
>>如果给出具体的数据，我们可以走一遍
35L 就是数据.
非要完整数据的话, 8L 给了个生成标准.
为了省事, 1~100000 即可.

hbmhalley

回复 67# pmerofc


    比如 1 3 2 4 5 7 6 8 9 11 10 12 ....
    这样基本有序的数据, 冒泡一遍就完了
    但插入排序的话, 每个都要从头扫到尾.

    另: 别拿我的代码测试. 我为了省事, 元素是倒着插的.

hbmhalley

回复 69# pmerofc


    所以说归并就是另一码事了

hbmhalley 发表于 2012-11-19 20:34
回复 11# pmerofc
    其次，使用冒泡是否妥当，个人倒觉得无可厚非，因为效率和 11L 是一样的，且原文是为了讲解
    如果是我，当然会选择归并排序 但这是另一码事了