近乎有序数组场景下Quick Sort与Merge Sort性能对比及优劣分析

咱们先直接给结论：在处理近乎有序的数组时，归并排序的性能表现会显著优于未做特殊优化的快速排序。下面拆解具体原因：

快速排序的“致命短板”在近乎有序场景下被放大 #

快速排序的核心逻辑依赖「分区（Partition）」操作——选一个基准值（Pivot），把数组分成比基准小和比基准大的两部分，再递归处理子数组。

• 如果数组近乎有序，要是咱们默认选数组的第一个/最后一个元素当基准，那分区结果会极端不平衡：其中一个子数组几乎是空的，另一个子数组包含了剩下的所有元素。
• 这种情况下，快速排序的时间复杂度会直接从理想的O(n log n)退化成O(n²)，递归树从平衡的二叉树变成了链表状，每一层递归只能减少一个元素的处理量，效率暴跌。
• 哪怕给快排加上「三数取中选基准」或者「随机选基准」的优化，能避免最坏时间复杂度，但因为数组本身近乎有序，分区过程中还是会产生大量不必要的元素交换操作，实际运行效率还是不如归并排序稳定。

归并排序的“天生优势”在近乎有序场景下被强化 #

归并排序的分治逻辑是严格将数组分成两半，不管数组本身有序与否，递归树始终是平衡的，时间复杂度稳定在O(n log n)。

• 更关键的是，归并排序的最后一步是「合并两个有序子数组」。在近乎有序的数组里，拆分出来的子数组本身就接近有序，合并时的元素比较、移动次数会比完全无序的情况少很多——相当于“捡了个便宜”，实际运行时间会比理论上的O(n log n)还要更快一点。
• 另外，归并排序是稳定排序（如果实现得当），在需要保留相同元素原始顺序的场景下，这也是额外的优势。

当然，你提到的没错，这种场景下还有更高效的算法——比如插入排序，因为近乎有序的数组中，每个元素只需要移动很少的次数就能到位，时间复杂度接近O(n)，比归并排序还要快。但回到你问的快排和归并的对比，归并的表现确实更优。

内容的提问来源于stack exchange，提问作者Jeffrey Yoshida