编辑“︁排序算法稳定性”︁

= 排序算法稳定性 =

'''排序算法的稳定性'''是指当待排序序列中存在多个具有相同关键字的元素时，排序后这些元素的相对顺序是否保持不变。稳定性是评估排序算法特性的重要指标之一，尤其在处理复合数据结构时具有重要意义。

== 定义 ==
给定一个序列 <math>S = [a_1, a_2, \ldots, a_n]</math>，其中元素 <math>a_i</math> 的关键字为 <math>k_i</math>。若排序后所有满足 <math>k_i = k_j</math> 且原始序列中 <math>i < j</math> 的元素对 <math>(a_i, a_j)</math> 仍保持 <math>a_i</math> 出现在 <math>a_j</math> 之前，则称该排序算法是'''稳定的'''；否则称为'''不稳定的'''。

== 为什么稳定性重要 ==
稳定性在以下场景中至关重要：
* '''多关键字排序'''：例如先按年龄排序，再按姓名排序时，需要保持年龄相同者的原始顺序。
* '''增量排序'''：当数据分批次到达时，稳定排序能保证已排序部分不受新数据影响。
* '''可视化与用户体验'''：表格连续排序时需要保持视觉一致性。

== 常见算法的稳定性分析 ==
以下是经典排序算法的稳定性分类：

=== 稳定算法 ===
* '''[[冒泡排序]]'''：相邻元素比较交换，不会改变相等元素的顺序。
* '''[[插入排序]]'''：元素逐个插入到已排序序列的正确位置。
* '''[[归并排序]]'''：合并操作中优先选取左子序列元素。
* '''[[计数排序]]'''和'''[[基数排序]]'''：非比较排序的稳定性由实现方式保证。

=== 不稳定算法 ===
* '''[[选择排序]]'''：交换操作可能破坏相等元素的相对位置。
* '''[[快速排序]]'''：分区过程中的交换会导致顺序变化。
* '''[[堆排序]]'''：堆结构调整会打乱相等元素的顺序。

== 代码示例 ==
以下通过Python示例演示稳定与不稳定排序的区别：

<syntaxhighlight lang="python">
# 原始数据：元组的第一项为排序关键字
data = [(3, '苹果'), (2, '香蕉'), (3, '橙子'), (1, '梨')]

# 稳定排序（插入排序实现）
def stable_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and arr[j][0] > key[0]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

print("稳定排序结果:", stable_sort(data.copy()))
# 输出: [(1, '梨'), (2, '香蕉'), (3, '苹果'), (3, '橙子')]

# 不稳定排序（选择排序实现）
def unstable_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j][0] < arr[min_idx][0]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print("不稳定排序结果:", unstable_sort(data.copy()))
# 可能输出: [(1, '梨'), (2, '香蕉'), (3, '橙子'), (3, '苹果')]
</syntaxhighlight>

== 可视化对比 ==
<mermaid>
graph LR
    A[原始顺序: (3,苹果), (3,橙子)] --> B[稳定排序]
    A --> C[不稳定排序]
    B --> D[保持顺序: (3,苹果), (3,橙子)]
    C --> E[可能反转: (3,橙子), (3,苹果)]
</mermaid>

== 实际应用案例 ==
'''电商平台价格排序'''：
1. 商品初始列表按上架时间排序
2. 用户点击"按价格排序"时：
   * 使用'''稳定排序'''：同价格商品保持原始上架顺序
   * 使用'''不稳定排序'''：同价格商品可能随机重排，导致用户体验不一致

'''多级排序系统'''：
<syntaxhighlight lang="python">
# 先按部门排序（稳定），再按薪资排序（稳定）
employees = [('销售', 5000), ('研发', 7000), ('销售', 4500)]
first_sort = sorted(employees, key=lambda x: x[0])  # 部门排序
final_sort = sorted(first_sort, key=lambda x: x[1]) # 保持部门内顺序
</syntaxhighlight>

== 数学形式化描述 ==
设原始序列中相等元素集合为 <math>E = \{a_p, a_q, \ldots\}</math> 且原始顺序满足 <math>p < q < \ldots</math>。稳定排序后的新索引 <math>f</math> 满足：
<math>
\forall a_i, a_j \in E, i < j \Rightarrow f(a_i) < f(a_j)
</math>

== 如何实现稳定性 ==
对于原本不稳定的算法，可通过以下方式改造：
1. '''扩展比较关键字'''：将元素原始位置作为次要比较项
2. '''使用指针排序'''：对元素引用进行排序而非直接操作数据
3. '''稳定化包装器'''：如Python的<code>sorted()</code>通过<code>timsort</code>实现稳定性

== 性能权衡 ==
{| class="wikitable"
|+ 稳定性与效率比较
! 算法类型 !! 平均时间复杂度 !! 稳定性 !! 空间复杂度
|-
| 归并排序 | <math>O(n \log n)</math> | 稳定 | <math>O(n)</math>
|-
| 快速排序 | <math>O(n \log n)</math> | 不稳定 | <math>O(\log n)</math>
|-
| 堆排序 | <math>O(n \log n)</math> | 不稳定 | <math>O(1)</math>
|}

== 总结 ==
理解排序算法的稳定性有助于：
* 正确选择适合场景的排序方法
* 设计高效的多级排序系统
* 避免在关键业务逻辑中出现意外行为
稳定性虽然可能带来轻微的性能开销，但在许多实际应用中值得优先考虑。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]