这是一个创建于 2518 天前的主题，其中的信息可能已经有所发展或是发生改变。
除了在数据量较小时，O(n^2) 排序也许常数上要优于 O(n * log(n)) 的算法。
还有啥时候可能会在工程里实际用到这些排序？
谢谢
还有啥时候可能会在工程里实际用到这些排序？
谢谢
第 1 条附言 · 2018-03-18 21:39:55 +08:00
咱们能不能接着讨论这个话题：
比如堆排序可以找第 K 大数（得益于堆的 O(1) 查询和 O(lg N) 删除) 再比如归并排序可以用来找逆序对
第 2 条附言 · 2018-03-18 21:41:15 +08:00
不一定要指平方级的排序算法
这个新问题是这样：各种排序算法除了真正排序之外还有啥有趣的应用
这个新问题是这样：各种排序算法除了真正排序之外还有啥有趣的应用
 |
1
forestyuan 2018-01-31 21:03:29 +08:00  2
好处是算法简单，我就特别喜欢用选择排序
|
 |
2
elgae 2018-01-31 22:28:30 +08:00
有在工程中使用冒泡的吗？
没有 |
 |
3
akira 2018-01-31 22:33:43 +08:00
大部分人，在大部分情况下 都用不到。
|
 |
4
zhuanzh 2018-01-31 22:35:18 +08:00 via Android
可以用于教学。
|
 |
5
Librazy 2018-01-31 23:20:40 +08:00 1
当数列“基本有序”的时候，可以选用冒泡排序。这个“基本有序”要看实际数据的来做 profiling 确定临界点。
|
 |
6
lhx2008 2018-01-31 23:26:32 +08:00 via Android 1
插入排序在数据几乎有序的时候效率是比较高的，而且是稳定的，易于实现，在没有轮子的情况下手造一个插排也很简单。但是有轮子的话当然是用轮子，java 就是快排和归并，当然递归到数据量小的时候也可能用了插排。
另外，插排也可以简单进化成希尔排序，它的效率也非常高。 当然还有就是算法本身的价值了，思路是可复用的。 |
 |
7
MrGba2z 2018-01-31 23:27:15 +08:00
用来找工作呀～这很实际吧
|
|
8
lhx2008 2018-01-31 23:33:53 +08:00 via Android 1
插排在数据（近乎）有序的时候是 o （ n ）的复杂度，空间复杂度也是 o （ n ），还是有优势的
|
 |
10
fox0001 2018-01-31 23:48:21 +08:00
一般在数据库查询时排好序，写代码排序的情况很少，自己实现排序算法的情况更少
|
 |
11
chengluyu 2018-01-31 23:50:26 +08:00 via iPad 3
根据快速排序选取 pivot 的方式可以构造相应的数据把其时间复杂度变成 O(n^2)，即使是随机选取 pivot 也有相应的攻击方式。因此比较成熟的语言库实现中都在数据量较小时使用插入排序，以增加算法时间复杂度上的稳定性。👈这是一个非常典型的应用。
另外插入排序在数据大致有序的情况下效果拔群…… 还有就是在一些嵌入式设备上，栈空间很小，数据量又小，非常适合用插入排序这种不需要空间的算法。 |
 |
13
h4lbhg1G 2018-02-01 00:44:35 +08:00 1
楼上正解 我没记错的话 C++的 STL 是 16 还是多少。教学上好像讲的是 9.
|
 |
14
GooMS 2018-02-01 00:54:24 +08:00 via Android
壓榨性能
|
 |
15
msg7086 2018-02-01 00:57:28 +08:00 2
|
 |
16
aheadlead OP @lhx2008 “当然还有就是算法本身的价值了，思路是可复用的。”
愿闻其详 @chengluyu 就因为快排这问题，所以曾经有一段时间不知不觉练就了 90 秒盲打一个堆排的能力。 关于 introsort，这点我有所了解，所以会在帖子里面提到在问题规模不大的时候，平方排序有常数优势。 @msg7086 我非好高骛远。纯粹是从工程的角度，考虑这些算法还有什么工程意义。楼上提到插入排序对于数据大致有序的问题，效果拔群，这点我确实没有想到，感谢楼上各位。 此外还有一个线性排序也很有趣。 https://zh.wikipedia.org/wiki/计数排序 适合数据比较集中的情况。 |
 |
17
gs139 2018-02-01 01:27:21 +08:00
“梦然”的歌，在这个浮躁的时代，专心搞音乐不炒作的已经不多了。
|
Select Language