排序算法
排序是最基础的算法问题之一：给定一组数据，按照升序或降序重新排列。Python 内置的 sorted()/list.sort() 已经能满足绝大多数实际开发需求，但理解冒泡、选择、插入这几种经典排序算法的实现原理，既能加深对"时间复杂度"“稳定性"等概念的理解，也是面试中的高频考点。本篇逐一实现这三种排序算法，并对比它们的性能特征。
排序算法概览
排序算法有两个关键指标：
- 稳定性：如果排序前
a在b前面，且两者值相等，排序后a是否仍在b前面。稳定排序在按多个字段排序时非常重要（比如先按姓名排序，再按分数排序时希望同分的人仍保持姓名序）。 - 时间复杂度：数据规模增长时，比较和交换次数的增长速度。
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
冒泡、选择、插入排序都基于"两两比较、就地交换”，思路直观，实现简单，但时间复杂度是 O(n²)，只适合小规模数据或教学场景；快速排序和归并排序基于分治思想，平均情况下更快，是生产级排序库的核心算法（Python 内置的 sorted() 使用的 Timsort 就是归并排序与插入排序的混合优化版本）。
冒泡排序（Bubble Sort）
交换思路
相邻元素两两比较，如果顺序不对就交换。每一趟比较结束后，本趟最大的元素会像气泡一样"浮"到无序区的最右端，有序区从右向左逐步扩大。
冒泡排序实现
def bubble_sort(nums: list[int]) -> list[int]:
"""就地冒泡排序，返回排序后的列表（升序）。"""
length = len(nums)
for i in range(length - 1): # i 控制比较的趟数
for j in range(length - 1 - i): # 每一趟无序区都缩小 1
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(bubble_sort([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]提前退出优化
如果某一趟比较中一次交换都没有发生，说明数据已经有序，可以提前结束：
def bubble_sort_v2(nums: list[int]) -> list[int]:
length = len(nums)
for i in range(length - 1):
swapped = False
for j in range(length - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
swapped = True
if not swapped: # 本趟没有发生交换，提前结束
break
return nums复杂度：最坏情况（逆序）需要比较 n(n-1)/2 次，时间复杂度 O(n²)；最好情况（已经有序）配合提前退出优化只需一趟 O(n)。相同元素之间不会发生交换，因此冒泡排序是稳定的。
选择排序（Selection Sort）
选出极值的思路
每一趟从无序区中找出最大值（或最小值）的下标，与无序区最左（或最右）端的元素交换，从而将有序区逐步扩大。
选择排序实现
def selection_sort(nums: list[int]) -> list[int]:
length = len(nums)
for i in range(length - 1):
min_index = i
for j in range(i + 1, length):
if nums[j] < nums[min_index]:
min_index = j
if min_index != i:
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums
print(selection_sort([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]进阶：二元选择排序
每一趟同时找出无序区的最小值和最大值，分别固定到无序区的左右两端，可以把比较趟数减半：
def selection_sort_dual(nums: list[int]) -> list[int]:
length = len(nums)
for i in range(length // 2):
left, right = i, length - 1 - i
min_index = max_index = left
for j in range(left, right + 1):
if nums[j] < nums[min_index]:
min_index = j
if nums[j] > nums[max_index]:
max_index = j
nums[left], nums[min_index] = nums[min_index], nums[left]
# 如果最大值恰好是刚被换到 left 位置的元素，索引需要同步更新
if max_index == left:
max_index = min_index
nums[right], nums[max_index] = nums[max_index], nums[right]
return nums
print(selection_sort_dual([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]复杂度：无论初始顺序如何，都需要完整比较 n(n-1)/2 次，时间复杂度恒为 O(n²)。相等元素在交换过程中可能被打乱相对顺序，因此选择排序是不稳定的。
插入排序（Insertion Sort）
哨兵位插入思路
将序列分为"有序区"（左侧）和"无序区"（右侧），每一趟取出无序区最左端的元素，从右向左在有序区中找到合适的位置插入。为了简化边界判断，可以在序列最前面加一个"哨兵位"暂存当前待插入的值。
插入排序实现
def insertion_sort(nums: list[int]) -> list[int]:
for i in range(1, len(nums)):
sentinel = nums[i] # 哨兵：本趟待插入的值
j = i - 1
while j >= 0 and nums[j] > sentinel:
nums[j + 1] = nums[j] # 比哨兵大，整体右移一位
j -= 1
nums[j + 1] = sentinel # 找到插入位置
return nums
print(insertion_sort([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]复杂度：最好情况（已经有序）每一趟只需比较一次，O(n)；最坏情况（逆序）需要 n(n-1)/2 次比较和移动，O(n²)。相同元素不会跨越彼此移动，因此插入排序是稳定的，且在小规模或"基本有序"的数据上效率很高（Timsort 正是利用了这一点，对小分区使用插入排序）。
如何选择
sorted(iterable, key=..., reverse=...) 或 list.sort() 即可——它们基于 Timsort，稳定且在真实数据上接近 O(n log n)。手写排序算法的价值在于理解算法原理、复杂度分析和面试准备，而不是替代标准库。nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
print(sorted(nums)) # 返回新列表，原列表不变
print(sorted(nums, key=lambda x: -x)) # 自定义排序规则
nums.sort() # 就地排序，返回 None