稳定排序

概述

稳定排序（Stable Sort） 是指在排序过程中保持相等元素之间原始相对顺序的排序算法。稳定性在某些应用场景中至关重要，例如多关键字排序。

定义

稳定排序

对于输入序列中任意两个值相等的元素 $a_i$ 和 $a_j$（$i<j$ 且 $a_i=a_j$），如果排序后 $a_i$ 仍然位于 $a_j$ 之前，则称该排序算法是稳定的。

形式化定义：排序算法是稳定的，当且仅当对于所有满足 $A[i]=A[j]$ 且 $i<j$ 的输入，排序后 $A[i]$ 的输出位置仍在 $A[j]$ 之前。

核心性质

常见排序算法的稳定性

排序算法	稳定性	时间复杂度
归并排序	稳定	$O(n\lg n)$
插入排序	稳定	$O(n^2)$
计数排序	稳定	$\Theta (n+k)$
基数排序	稳定	$\Theta (d(n+k))$
桶排序	稳定（取决于桶内排序）	期望 $O(n)$
快速排序	不稳定	期望 $O(n\lg n)$
堆排序	不稳定	$O(n\lg n)$

为什么稳定性重要？

1. 多关键字排序：当需要按多个关键字排序时（如先按姓、再按名），稳定性保证第二趟排序不会破坏第一趟排序的结果。
2. 基数排序的前提：基数排序 的正确性依赖于子排序算法的稳定性。
3. 保持关联数据：当排序的元素携带附加信息时，稳定性保证附加信息与元素的对应关系不被打乱。

不稳定排序的补救

不稳定排序算法（如快速排序）可以通过扩展键值（将原始位置作为次要键值）来模拟稳定性，但这会增加额外开销。

章节扩展

第8章：线性时间排序

稳定性概念在第8章尤为重要，因为 计数排序 和 基数排序 的正确性和高效性都依赖于稳定性。

参见

• 归并排序
• 计数排序
• 基数排序
• 快速排序
• 堆排序