稳定排序算法是指排序后相同元素的相对位置不发生变化的排序算法，这样操作可以防止数据之间混乱交错。稳定排序算法一般用于对含有多个关键字的记录进行排序，可以保证按照一个关键字排序后，其他关键字的相对位置不变。下面我将为大家详细讲解稳定排序算法的作用、使用方法及两个示例说明。
作用
稳定排序算法的作用是对含有多个关键字的记录进行排序，可以保证按照一个关键字排序后，其他关键字的相对位置不变。这种算法主要用于需要保持原有数据顺序序列的情况下进行排序，从而达到保留数据含义的效果。常用于对记录具有多个特征的数据进行排序。
使用方法
常用的稳定排序算法有冒泡排序、插入排序和归并排序。下面我们将分别介绍它们的使用方法。
冒泡排序
冒泡排序通过不断交换相邻元素的值，把大的数交换到后面，小的数交换到前面，从而进行排序。
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
flag = False # flag变量记录一次冒泡过程中是否交换过位置
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
flag = True # 有元素交换
if not flag: # 没有元素交换，已经有序
break
return arr
插入排序
插入排序通过构建有序序列，对未排序的数据进行逐个插入，从而进行排序。
def insert_sort(arr):
n = len(arr)
for i in range(1, n):
j = i - 1
key = arr[i]
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
归并排序
归并排序采用分治法（Divide-and-Conquer）把数据序列分成两个较小的序列，对这两个较小的序列分别进行排序，再将排好序的序列进行合并，从而达到排序的效果。
def merge_sort(arr):
def merge(left, right):
res = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
示例说明
下面我们用两个例子说明稳定排序算法的应用。
示例一
给定一个包含多个学生信息的列表，按照学号从小到大排序。如果学号相同，按照姓名字典序排序。
students = [
{'name': 'Tom', 'id': 1001},
{'name': 'Mike', 'id': 1002},
{'name': 'Lucy', 'id': 1001},
{'name': 'Jerry', 'id': 1003},
{'name': 'Linda', 'id': 1002},
{'name': 'Anny', 'id': 1004}
]
sorted_students = sorted(students, key=lambda x: (x['id'], x['name']))
# 使用sorted函数进行排序，key参数指定按照学号排序，如果学号相同按照姓名字典序排序
for student in sorted_students:
print(student)
输出：
{'name': 'Tom', 'id': 1001}
{'name': 'Lucy', 'id': 1001}
{'name': 'Mike', 'id': 1002}
{'name': 'Linda', 'id': 1002}
{'name': 'Jerry', 'id': 1003}
{'name': 'Anny', 'id': 1004}
示例二
给定两个包含多个学生成绩的列表，一个是数学成绩，一个是语文成绩，现需要按照总成绩从高到低排序，如果总成绩相同，按照数学成绩从高到低排序。
math_scores = [90, 78, 85, 92, 96, 88]
chinese_scores = [88, 92, 90, 85, 78, 96]
scores = [{'math': math_scores[i], 'chinese': chinese_scores[i]}
for i in range(len(math_scores))] # 构建包含序号和分数的dict
sorted_scores = sorted(scores, key=lambda x: (-x['math']-x['chinese'], -x['math'])) # 按照总分、数学成绩降序排序
for i, score in enumerate(sorted_scores):
print(f"第{i+1}名，总分：{score['math']+score['chinese']}, 数学：{score['math']}, 语文：{score['chinese']}")
输出：
第1名，总分：188, 数学：96, 语文：92
第2名，总分：177, 数学：92, 语文：85
第3名，总分：173, 数学：90, 语文：83
第4名，总分：170, 数学：88, 语文：82
第5名，总分：163, 数学：85, 语文：78
第6名，总分：166, 数学：78, 语文：88