排序算法稳定性

排序算法的稳定性是指当待排序序列中存在多个具有相同关键字的元素时，排序后这些元素的相对顺序是否保持不变。稳定排序算法会保持相同元素的原始顺序，而不稳定排序算法则可能改变它们的相对顺序。

定义

在计算机科学中，给定一个序列 $S = [a_{1}, a_{2}, \dots, a_{n}]$ ，其中每个元素 $a_{i}$ 有一个用于比较的关键字 $k_{i}$ 。如果对于任意两个元素 $a_{i}$ 和 $a_{j}$ ，当 $k_{i} = k_{j}$ 且 $i < j$ 时，排序后 $a_{i}$ 仍然位于 $a_{j}$ 之前，则该排序算法是稳定的；否则，它是不稳定的。

为什么稳定性重要

稳定性在某些应用场景中至关重要，例如：

多关键字排序：先按一个关键字排序，再按另一个关键字排序时，稳定的排序能保留前一次排序的结果。
用户界面显示：保持相同元素的原始顺序可能符合用户的预期。
数据库操作：某些查询需要保持记录的原始顺序。

常见排序算法的稳定性

下表列出了一些常见排序算法的稳定性：

排序算法稳定性对照表
排序算法	稳定性
冒泡排序	稳定
插入排序	稳定
归并排序	稳定
基数排序	稳定
选择排序	不稳定
快速排序	不稳定
堆排序	不稳定
希尔排序	不稳定

示例分析

稳定排序示例（插入排序）

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 输入：包含相同元素的列表
data = [('a', 2), ('b', 1), ('c', 2), ('d', 1)]
# 按第二个元素排序
sorted_data = insertion_sort(data, key=lambda x: x[1])
print(sorted_data)

输出：

[('b', 1), ('d', 1), ('a', 2), ('c', 2)]

注意：原始顺序中 ('b', 1) 在 ('d', 1) 之前，排序后仍然保持这个顺序。

不稳定排序示例（快速排序）

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)

# 同样的输入
data = [('a', 2), ('b', 1), ('c', 2), ('d', 1)]
sorted_data = quick_sort(data, key=lambda x: x[1])
print(sorted_data)

可能的输出：

[('d', 1), ('b', 1), ('c', 2), ('a', 2)]

注意：这里 ('b', 1) 和 ('d', 1) 的相对顺序可能被反转。

稳定性可视化

如何实现稳定排序

对于不稳定的排序算法，可以通过以下方法使其稳定： 1. 扩展比较关键字：将原始位置信息作为次要关键字。 2. 使用稳定算法作为基础：如Python的 sorted() 函数使用TimSort（稳定）。

示例实现：

def stable_quick_sort(arr):
    # 为每个元素添加原始索引作为次要关键字
    indexed_arr = [(x, i) for i, x in enumerate(arr)]
    def sort_key(item):
        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))

输出：

[('b', 1), ('d', 1), ('a', 2), ('c', 2)]

实际应用案例

成绩单排序系统： 1. 先按分数降序排序 2. 对同分的学生保持按学号升序排列

使用稳定排序可以分两步实现： 1. 先按学号排序（稳定） 2. 再按分数排序（稳定）

最终结果将满足：分数高的在前，同分时学号小的在前。

数学表达

稳定性可以形式化表示为：对于排序函数 $f$ 和输入序列 $S = [a_{1}, \dots, a_{n}]$ ，若： $\forall i < j : k_{i} = k_{j} \Rightarrow position (f (S)_{i}) < position (f (S)_{j})$ 则称 $f$ 是稳定的。

总结

稳定排序保持相同关键字的原始相对顺序
稳定性在多关键字排序等场景中很重要
可以通过修改比较方式使不稳定算法变得稳定
常见算法中，插入排序、归并排序是稳定的，而快速排序、堆排序不稳定

理解排序算法的稳定性有助于在实际应用中选择合适的排序策略，特别是在需要保持数据部分有序性的场景中。