数据结构 排序的稳定性

### 数据结构排序算法稳定性解释

#### 稳定性定义
在一个待排序的序列中，如果存在多个具有相同键值的关键字，在完成排序之后这些相同键值的关键字相对位置保持不变，则称这种排序算法是稳定的。反之则是不稳定的[^3]。

#### 影响因素
当执行排序操作时，对于两个相等元素A和B，假设原始输入中A位于B之前；那么在最终输出的结果里：

- 如果仍然维持这个顺序关系（即A依然处于B前），则说明所使用的排序方式具备稳定性；
- 若改变了这一先后次序，则表明该种排序不具备稳定性[^2]。

#### 示例展示
考虑一组学生考试成绩如下表所示，其中姓名作为辅助字段用于区分同分数的学生：

| 成绩 | 姓名 |
| --- | ---- |
| 89 | 小明|
| 76 | 小红|
| 76 | 小刚|

应用不同类型的排序方法对其进行升序排列后的结果对比：

##### 使用稳定排序算法（如冒泡排序）

| 排名 | 成绩 | 姓名 |
|----|-----|------|
| 1 | 76 | 小红 |
| 2 | 76 | 小刚 |
| 3 | 89 | 小明 |

可以看到，即使两人得分一样，“小红”依旧排在“小刚”的前面，这体现了排序过程中对原有顺序进行了保留。

##### 使用不稳定排序算法（比如堆排序）

| 排名 | 成绩 | 姓名 |
|----|-----|------|
| 1 | 76 | 小刚 |
| 2 | 76 | 小红 |
| 3 | 89 | 小明 |

这里虽然整体上实现了从小到大的正确排序，但对于相同的`76`分而言，“小刚”被移动到了“小红”之前，破坏了原有的前后关系。

#### 稳定性和非稳定性排序算法列举

- **稳定**：归并排序、插入排序、冒泡排序等。

- **不稳定**：快速排序、希尔排序、选择排序、堆排序等。

def merge_sort(arr):
    """这是一个典型的稳定排序算法的例子"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr)//2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    sorted_arr = []
    while left_half and right_half:
        if (left_half[0][1], left_half[0]) <= (right_half[0][1], right_half[0]):
            sorted_arr.append(left_half.pop(0))
        else:
            sorted_arr.append(right_half.pop(0))

    # 添加剩余项
    sorted_arr.extend(left_half or right_half)

    return sorted_arr


data_with_duplicates = [(89,'a'), (76,'b'), (76,'c')]
print("Original:", data_with_duplicates)
sorted_data = merge_sort(data_with_duplicates.copy())
print("Sorted by Merge Sort(stable):", sorted_data)