何时及为何选择简单排序算法（O(N²)）而非高级排序算法（O(N log N)）？

这是个非常务实的问题——很多开发者容易陷入“复杂度至上”的误区，却忽略了实际工程中算法的常数开销、场景适配性这些关键细节。下面就梳理几种更适合使用插入排序、冒泡排序这类简单O(N²)算法的场景：

1. 处理极小规模的数据集 #

当你要排序的元素数量非常少（比如几十甚至上百个，具体阈值取决于语言和硬件），O(N²)算法的实际运行速度往往比O(N log N)算法更快。

比如你提到的20个元素的场景：像快速排序这类算法，需要递归调用、分区操作，还有 pivot 选择的额外逻辑，这些都会带来不小的常数开销；而插入排序只是简单的循环、元素移动，代码紧凑，CPU缓存命中率更高。实际测试中，当N小于50左右时，插入排序的执行效率通常超过快排。很多工业级排序实现（比如Java的Arrays.sort）都做了类似优化：当递归到子数组规模足够小时，自动切换为插入排序。

2. 数据集已经接近有序（或部分有序） #

简单排序算法的最优时间复杂度往往更贴合这类场景：

• 插入排序在数组完全有序时，时间复杂度是O(N)，只需要一次遍历确认即可；即使数组只有少量元素错位，也只需要做几次元素移动。
• 冒泡排序在完全有序的数组中，同样只需要一次遍历就能完成。

而反观快排、归并排序这类O(N log N)算法，不管数组有序与否，都要执行完整的分区/合并流程，甚至快排在数组完全有序时还会触发最坏情况（退化为O(N²)），效率远不如插入排序。

3. 内存空间极度受限的环境 #

很多高级排序算法需要额外的内存开销：

• 归并排序需要O(N)的辅助数组来存储中间结果；
• 快速排序的递归调用会占用栈空间（递归深度为O(log N)）。

而插入排序、选择排序都是原地排序算法，只需要常数级的额外空间（O(1)）。在嵌入式设备、单片机这类内存资源极其紧张的场景下，简单排序的内存优势是决定性的。

4. 优先考虑开发效率与代码可维护性 #

有时候工程开发中，性能并非唯一考量因素。如果只是需要一个小型排序功能，插入排序的代码可能几行就能实现，逻辑清晰易懂；而快速排序需要处理分区、递归，还要考虑随机化 pivot 避免最坏情况，代码复杂度高得多。

当数据集规模不大，性能差异可以忽略时，简单排序的开发成本更低，后续维护也更简单，不容易出现bug。

5. 元素比较成本极高的场景 #

如果要排序的元素是复杂对象，比较两个元素的代价非常大（比如需要执行复杂计算、甚至IO操作），那么减少比较次数比降低时间复杂度量级更重要。

比如在数组接近有序时，插入排序只需要O(N)次比较，而快排依然需要O(N log N)次比较。这种情况下，即使O(N²)的时间复杂度量级更高，但实际的比较总开销反而更小，整体效率更高。

内容的提问来源于stack exchange，提问作者Fresh Java