2025年5月12日 (一) 00:27的最新版本

排序算法稳定性[编辑 | 编辑源代码]

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

定义[编辑 | 编辑源代码]

给定一个序列 $S = [a_{1}, a_{2}, \dots, a_{n}]$ ，其中元素 $a_{i}$ 的关键字为 $k_{i}$ 。若排序后所有满足 $k_{i} = k_{j}$ 且原始序列中 $i < j$ 的元素对 $(a_{i}, a_{j})$ 仍保持 $a_{i}$ 出现在 $a_{j}$ 之前，则称该排序算法是稳定的；否则称为不稳定的。

为什么稳定性重要[编辑 | 编辑源代码]

稳定性在以下场景中至关重要：

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

常见算法的稳定性分析[编辑 | 编辑源代码]

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

稳定算法[编辑 | 编辑源代码]

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

不稳定算法[编辑 | 编辑源代码]

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

代码示例[编辑 | 编辑源代码]

以下通过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, '苹果')]

可视化对比[编辑 | 编辑源代码]

实际应用案例[编辑 | 编辑源代码]

电商平台价格排序： 1. 商品初始列表按上架时间排序 2. 用户点击"按价格排序"时：

  * 使用稳定排序：同价格商品保持原始上架顺序
  * 使用不稳定排序：同价格商品可能随机重排，导致用户体验不一致

多级排序系统：

# 先按部门排序（稳定），再按薪资排序（稳定）
employees = [('销售', 5000), ('研发', 7000), ('销售', 4500)]
first_sort = sorted(employees, key=lambda x: x[0])  # 部门排序
final_sort = sorted(first_sort, key=lambda x: x[1]) # 保持部门内顺序

数学形式化描述[编辑 | 编辑源代码]

设原始序列中相等元素集合为 $E = {a_{p}, a_{q}, \dots}$ 且原始顺序满足 $p < q < \dots$ 。稳定排序后的新索引 $f$ 满足： $\forall a_{i}, a_{j} \in E, i < j \Rightarrow f (a_{i}) < f (a_{j})$

如何实现稳定性[编辑 | 编辑源代码]

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

性能权衡[编辑 | 编辑源代码]

稳定性与效率比较
算法类型	平均时间复杂度	稳定性	空间复杂度
$O (n \log n)$ \| 稳定 \| $O (n)$
$O (n \log n)$ \| 不稳定 \| $O (\log n)$
$O (n \log n)$ \| 不稳定 \| $O (1)$

总结[编辑 | 编辑源代码]

理解排序算法的稳定性有助于：

正确选择适合场景的排序方法
设计高效的多级排序系统
避免在关键业务逻辑中出现意外行为

稳定性虽然可能带来轻微的性能开销，但在许多实际应用中值得优先考虑。

@@ 第1行： / 第1行： @@
 = 排序算法稳定性 =
-'''排序算法的稳定性'''是指当待排序序列中存在多个具有相同关键字的元素时，排序后这些元素的相对顺序是否保持不变。稳定排序算法会保持相同元素的原始顺序，而不稳定排序算法则可能改变它们的相对顺序。
+'''排序算法的稳定性'''是指当待排序序列中存在多个具有相同关键字的元素时，排序后这些元素的相对顺序是否保持不变。稳定性是评估排序算法特性的重要指标之一，尤其在处理复合数据结构时具有重要意义。
 == 定义 ==
-在计算机科学中，给定一个序列 <math>S = [a_1, a_2, \ldots, a_n]</math>，其中每个元素 <math>a_i</math> 有一个用于比较的'''关键字''' <math>k_i</math>。如果对于任意两个元素 <math>a_i</math> 和 <math>a_j</math>，当 <math>k_i = k_j</math> 且 <math>i < j</math> 时，排序后 <math>a_i</math> 仍然位于 <math>a_j</math> 之前，则该排序算法是'''稳定的'''；否则，它是不稳定的。
+给定一个序列 <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> 之前，则称该排序算法是'''稳定的'''；否则称为'''不稳定的'''。
 == 为什么稳定性重要 ==
-稳定性在某些应用场景中至关重要，例如：
+稳定性在以下场景中至关重要：
-* '''多关键字排序'''：先按一个关键字排序，再按另一个关键字排序时，稳定的排序能保留前一次排序的结果。
+* '''多关键字排序'''：例如先按年龄排序，再按姓名排序时，需要保持年龄相同者的原始顺序。
-* '''用户界面显示'''：保持相同元素的原始顺序可能符合用户的预期。
+* '''增量排序'''：当数据分批次到达时，稳定排序能保证已排序部分不受新数据影响。
-* '''数据库操作'''：某些查询需要保持记录的原始顺序。
+* '''可视化与用户体验'''：表格连续排序时需要保持视觉一致性。
-== 常见排序算法的稳定性 ==
+== 常见算法的稳定性分析 ==
-下表列出了一些常见排序算法的稳定性：
+以下是经典排序算法的稳定性分类：
-{| class="wikitable"
+=== 稳定算法 ===
-|+ 排序算法稳定性对照表
+* '''[[冒泡排序]]'''：相邻元素比较交换，不会改变相等元素的顺序。
-! 排序算法 !! 稳定性
+* '''[[插入排序]]'''：元素逐个插入到已排序序列的正确位置。
-|-
+* '''[[归并排序]]'''：合并操作中优先选取左子序列元素。
-| [[冒泡排序]] || 稳定
+* '''[[计数排序]]'''和'''[[基数排序]]'''：非比较排序的稳定性由实现方式保证。
-|-
-| [[插入排序]] || 稳定
+=== 不稳定算法 ===
-|-
+* '''[[选择排序]]'''：交换操作可能破坏相等元素的相对位置。
-| [[归并排序]] || 稳定
+* '''[[快速排序]]'''：分区过程中的交换会导致顺序变化。
-|-
+* '''[[堆排序]]'''：堆结构调整会打乱相等元素的顺序。
-| [[基数排序]] || 稳定
-|-
+== 代码示例 ==
-| [[选择排序]] || 不稳定
+以下通过Python示例演示稳定与不稳定排序的区别：
-|-
-| [[快速排序]] || 不稳定
-|-
-| [[堆排序]] || 不稳定
-|-
-| [[希尔排序]] || 不稳定
-|}
-== 示例分析 ==
-=== 稳定排序示例（插入排序） ===
 <syntaxhighlight lang="python">
-def insertion_sort(arr):
+# 原始数据：元组的第一项为排序关键字
+data = [(3, '苹果'), (2, '香蕉'), (3, '橙子'), (1, '梨')]
+# 稳定排序（插入排序实现）
+def stable_sort(arr):
      for i in range(1, len(arr)):
          key = arr[i]
-         j = i - 1
+         j = i-1
-         while j >= 0 and arr[j] > key:
+         while j >=0 and arr[j][0] > key[0]:
-             arr[j + 1] = arr[j]
+             arr[j+1] = arr[j]
              j -= 1
-         arr[j + 1] = key
+         arr[j+1] = key
      return arr
-# 输入：包含相同元素的列表
+print("稳定排序结果:", stable_sort(data.copy()))
-data = [('a', 2), ('b', 1), ('c', 2), ('d', 1)]
+# 输出: [(1, '梨'), (2, '香蕉'), (3, '苹果'), (3, '橙子')]
-# 按第二个元素排序
-sorted_data = insertion_sort(data, key=lambda x: x[1])
-print(sorted_data)
-</syntaxhighlight>
-'''输出：'''
+# 不稳定排序（选择排序实现）
-<pre>
+def unstable_sort(arr):
-[('b', 1), ('d', 1), ('a', 2), ('c', 2)]
+    for i in range(len(arr)):
-</pre>
+        min_idx = i
+        for j in range(i+1, len(arr)):
-注意：原始顺序中 <code>('b', 1)</code> 在 <code>('d', 1)</code> 之前，排序后仍然保持这个顺序。
+            if arr[j][0] < arr[min_idx][0]:
+                min_idx = j
-=== 不稳定排序示例（快速排序） ===
+        arr[i], arr[min_idx] = arr[min_idx], arr[i]
-<syntaxhighlight lang="python">
+     return arr
-def quick_sort(arr):
-    if len(arr) <= 1:
-        return arr
-    pivot = arr[len(arr) // 2]
-    left = [x for x in arr if x < pivot]
-    middle = [x for x in arr if x == pivot]
-    right = [x for x in arr if x > pivot]
-     return quick_sort(left) + middle + quick_sort(right)
-# 同样的输入
+print("不稳定排序结果:", unstable_sort(data.copy()))
-data = [('a', 2), ('b', 1), ('c', 2), ('d', 1)]
+# 可能输出: [(1, '梨'), (2, '香蕉'), (3, '橙子'), (3, '苹果')]
-sorted_data = quick_sort(data, key=lambda x: x[1])
-print(sorted_data)
 </syntaxhighlight>
-'''可能的输出：'''
+== 可视化对比 ==
-<pre>
-[('d', 1), ('b', 1), ('c', 2), ('a', 2)]
-</pre>
-注意：这里 <code>('b', 1)</code> 和 <code>('d', 1)</code> 的相对顺序可能被反转。
-== 稳定性可视化 ==
 <mermaid>
-graph TD
+graph LR
-     A[原始序列: (a,2), (b,1), (c,2), (d,1)] --> B[稳定排序]
+     A[原始顺序: (3,苹果), (3,橙子)] --> B[稳定排序]
      A --> C[不稳定排序]
-     B --> D[结果: (b,1), (d,1), (a,2), (c,2)]
+     B --> D[保持顺序: (3,苹果), (3,橙子)]
-     C --> E[可能结果: (d,1), (b,1), (c,2), (a,2)]
+     C --> E[可能反转: (3,橙子), (3,苹果)]
 </mermaid>
-== 如何实现稳定排序 ==
+== 实际应用案例 ==
-对于不稳定的排序算法，可以通过以下方法使其稳定：
+'''电商平台价格排序'''：
-. 扩展比较关键字：将原始位置信息作为次要关键字。
+. 商品初始列表按上架时间排序
-. 使用稳定算法作为基础：如Python的 <code>sorted()</code> 函数使用TimSort（稳定）。
+. 用户点击"按价格排序"时：
+   * 使用'''稳定排序'''：同价格商品保持原始上架顺序
+   * 使用'''不稳定排序'''：同价格商品可能随机重排，导致用户体验不一致
-示例实现：
+'''多级排序系统'''：
 <syntaxhighlight lang="python">
-def stable_quick_sort(arr):
+# 先按部门排序（稳定），再按薪资排序（稳定）
-    # 为每个元素添加原始索引作为次要关键字
+employees = [('销售', 5000), ('研发', 7000), ('销售', 4500)]
-    indexed_arr = [(x, i) for i, x in enumerate(arr)]
+first_sort = sorted(employees, key=lambda x: x[0])  # 部门排序
-    def sort_key(item):
+final_sort = sorted(first_sort, key=lambda x: x[1]) # 保持部门内顺序
-        return (item[0][1], item[1])  # 主关键字 + 原始索引
-    return [x[0] for x in sorted(indexed_arr, key=sort_key)]
-data = [('a', 2), ('b', 1), ('c', 2), ('d', 1)]
-print(stable_quick_sort(data))
 </syntaxhighlight>
-'''输出：'''
+== 数学形式化描述 ==
-<pre>
+设原始序列中相等元素集合为 <math>E = \{a_p, a_q, \ldots\}</math> 且原始顺序满足 <math>p < q < \ldots</math>。稳定排序后的新索引 <math>f</math> 满足：
-[('b', 1), ('d', 1), ('a', 2), ('c', 2)]
+<math>
-</pre>
+\forall a_i, a_j \in E, i < j \Rightarrow f(a_i) < f(a_j)
+</math>
-== 实际应用案例 ==
+== 如何实现稳定性 ==
-'''成绩单排序系统'''：
+对于原本不稳定的算法，可通过以下方式改造：
-. 先按分数降序排序
+. '''扩展比较关键字'''：将元素原始位置作为次要比较项
-. 对同分的学生保持按学号升序排列
+. '''使用指针排序'''：对元素引用进行排序而非直接操作数据
+. '''稳定化包装器'''：如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>f</math> 和输入序列 <math>S = [a_1, \ldots, a_n]</math>，若：
+|-
-<math>
+| 堆排序 | <math>O(n \log n)</math> | 不稳定 | <math>O(1)</math>
-\forall i < j : k_i = k_j \Rightarrow \text{position}(f(S)_i) < \text{position}(f(S)_j)
+|}
-</math>
-则称 <math>f</math> 是稳定的。
 == 总结 ==
-* 稳定排序保持相同关键字的原始相对顺序
+理解排序算法的稳定性有助于：
-* 稳定性在多关键字排序等场景中很重要
+* 正确选择适合场景的排序方法
-* 可以通过修改比较方式使不稳定算法变得稳定
+* 设计高效的多级排序系统
-* 常见算法中，插入排序、归并排序是稳定的，而快速排序、堆排序不稳定
+* 避免在关键业务逻辑中出现意外行为
+稳定性虽然可能带来轻微的性能开销，但在许多实际应用中值得优先考虑。
-理解排序算法的稳定性有助于在实际应用中选择合适的排序策略，特别是在需要保持数据部分有序性的场景中。
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
 [[Category:排序算法]]