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

[aheadlead]

除了在数据量较小时，O(n^2) 排序也许常数上要优于 O(n * log(n)) 的算法。

还有啥时候可能会在工程里实际用到这些排序？

谢谢

[forestyuan]

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

[elgae]

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

[akira]

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

[zhuanzh]

可以用于教学。

[Librazy]

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

[lhx2008]

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

[MrGba2z]

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

[lhx2008]

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

[lhx2008]

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

[fox0001]

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

[chengluyu]

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

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

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

[chengluyu]

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

[h4lbhg1G]

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

[GooMS]

壓榨性能

[msg7086]

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

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

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

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

[aheadlead]

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


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


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


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

[gs139]

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