选择排序、插入排序、冒泡排序等 O(n^2) 的排序有什么实际应用？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2488 天前的主题，其中的信息可能已经有所发展或是发生改变。

除了在数据量较小时，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

不一定要指平方级的排序算法

这个新问题是这样：各种排序算法除了真正排序之外还有啥有趣的应用

排序

常数

冒泡

log

17 条回复 • 2018-02-01 01:27:21 +08:00

forestyuan

2018-01-31 21:03:29 +08:00

好处是算法简单，我就特别喜欢用选择排序

elgae

2018-01-31 22:28:30 +08:00

有在工程中使用冒泡的吗？
没有

akira

2018-01-31 22:33:43 +08:00

大部分人，在大部分情况下都用不到。

zhuanzh

2018-01-31 22:35:18 +08:00 via Android

可以用于教学。

Librazy

2018-01-31 23:20:40 +08:00

当数列“基本有序”的时候，可以选用冒泡排序。这个“基本有序”要看实际数据的来做 profiling 确定临界点。

lhx2008

2018-01-31 23:26:32 +08:00 via Android

插入排序在数据几乎有序的时候效率是比较高的，而且是稳定的，易于实现，在没有轮子的情况下手造一个插排也很简单。但是有轮子的话当然是用轮子，java 就是快排和归并，当然递归到数据量小的时候也可能用了插排。
另外，插排也可以简单进化成希尔排序，它的效率也非常高。
当然还有就是算法本身的价值了，思路是可复用的。

MrGba2z

2018-01-31 23:27:15 +08:00

用来找工作呀～这很实际吧

lhx2008

2018-01-31 23:33:53 +08:00 via Android

插排在数据（近乎）有序的时候是 o （ n ）的复杂度，空间复杂度也是 o （ n ），还是有优势的

lhx2008

2018-01-31 23:36:26 +08:00 via Android

@lhx2008 辅助的空间复杂度应该是 o1

fox0001

2018-01-31 23:48:21 +08:00

一般在数据库查询时排好序，写代码排序的情况很少，自己实现排序算法的情况更少

chengluyu

2018-01-31 23:50:26 +08:00 via iPad

根据快速排序选取 pivot 的方式可以构造相应的数据把其时间复杂度变成 O(n^2)，即使是随机选取 pivot 也有相应的攻击方式。因此比较成熟的语言库实现中都在数据量较小时使用插入排序，以增加算法时间复杂度上的稳定性。👈这是一个非常典型的应用。

另外插入排序在数据大致有序的情况下效果拔群……

还有就是在一些嵌入式设备上，栈空间很小，数据量又小，非常适合用插入排序这种不需要空间的算法。

chengluyu

2018-01-31 23:53:08 +08:00 via iPad

@chengluyu 对了，这种快速排序混着别的排序的算法叫做 introsort。

h4lbhg1G

2018-02-01 00:44:35 +08:00

楼上正解我没记错的话 C++的 STL 是 16 还是多少。教学上好像讲的是 9.

GooMS

2018-02-01 00:54:24 +08:00 via Android

壓榨性能

msg7086

2018-02-01 00:57:28 +08:00

@chengluyu 有中文翻译成内省排序的。

@aheadlead 算法都是从简单到难的，不可能刚开始直接教你跳舞树什么的吧。以前科技不发达的时候，人们只知道这些简单的排序算法，后来一点点发现性能越来越好的，于是老办法就都淘汰了，只用来教学使用。

比如说高中时候证明函数单调性，用两个函数相减然后判断变量范围的方法来做。
到了后来学了微积分，同样的题目一阶导数下去一把梭就得了，就犯不着再用原来的办法了。

O(n^2)排序也逐渐成为了教科书算法，常常作为反例，告诉你哪些算法太 naïve，自己写代码的时候要小心了。

aheadlead

2018-02-01 01:16:14 +08:00

@lhx2008 “当然还有就是算法本身的价值了，思路是可复用的。”
愿闻其详

@chengluyu 就因为快排这问题，所以曾经有一段时间不知不觉练就了 90 秒盲打一个堆排的能力。
关于 introsort，这点我有所了解，所以会在帖子里面提到在问题规模不大的时候，平方排序有常数优势。

@msg7086 我非好高骛远。纯粹是从工程的角度，考虑这些算法还有什么工程意义。楼上提到插入排序对于数据大致有序的问题，效果拔群，这点我确实没有想到，感谢楼上各位。

此外还有一个线性排序也很有趣。
https://zh.wikipedia.org/wiki/计数排序
适合数据比较集中的情况。

gs139

2018-02-01 01:27:21 +08:00

“梦然”的歌，在这个浮躁的时代，专心搞音乐不炒作的已经不多了。