排序算法详细学习版：从基础到精通
首发 2026/05/06
阅读 20
评论 0
更新 2026/05/10
排序算法详细学习版：从基础到精通
目标：从零理解常见排序算法，能写代码、能分析复杂度、能在面试中说清楚。
代码语言：Python。
编写重点：每段代码都有清晰注释，说明变量作用和每一步在做什么。
1. 排序算法总览
排序就是把一组数据按某种规则重新排列。
常见规则：
text
升序：从小到大
降序：从大到小
按字段排序：比如按年龄、分数、时间排序常见排序可以分成两大类：
text
1. 比较排序：靠元素之间两两比较大小来排序
2. 非比较排序：利用数字范围、桶、位数等信息来排序比较排序包括：
text
冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序非比较排序包括：
text
计数排序、桶排序、基数排序2. 复杂度总表
| 排序算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 是否原地 | 掌握程度 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 原地 | 入门必须懂 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 原地 | 入门必须懂 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 原地 | 入门必须懂 |
| 希尔排序 | 约 O(n^1.3) ~ O(n²) | O(n²) | O(1) | 不稳定 | 原地 | 了解 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 通常非原地 | 重点 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 原地 | 重点 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 原地 | 重点 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 可稳定 | 通常非原地 | 了解场景 |
| 桶排序 | 平均 O(n + k) | O(n²) | O(n + k) | 可稳定 | 非原地 | 了解场景 |
| 基数排序 | O(d × (n + k)) | O(d × (n + k)) | O(n + k) | 稳定 | 非原地 | 了解场景 |
| Python sort | O(n log n) | O(n log n) | O(n) | 稳定 | sort 原地 | 刷题常用 |
说明：
text
n：元素数量
k：数据范围或桶数量
d：数字位数3. 排序中几个关键概念
3.1 稳定排序
如果两个元素值相等，排序后它们的相对顺序不变，就叫稳定排序。
比如：
text
原数据：
[('张三', 90), ('李四', 90), ('王五', 80)]
按分数升序排序后：
[('王五', 80), ('张三', 90), ('李四', 90)]张三和李四分数一样，排序后张三仍然在李四前面，这就是稳定。
常见稳定排序：
text
冒泡排序、插入排序、归并排序、计数排序、基数排序、Python sort常见不稳定排序：
text
选择排序、快速排序、堆排序、希尔排序3.2 原地排序
如果排序过程中只使用常数级额外空间，就叫原地排序。
比如：
text
冒泡排序：原地
选择排序：原地
插入排序：原地
堆排序：原地
归并排序：通常不是原地，因为需要辅助数组3.3 自适应排序
如果数组本来接近有序，算法会跑得更快，叫自适应排序。
典型：
text
插入排序
优化版冒泡排序
Python 的 Timsort4. Python 内置排序
刷 LeetCode 时，只要题目不是专门考你手写排序，通常可以直接用内置排序。
4.1 nums.sort()
python
nums = [3, 1, 2]
# nums.sort() 会原地修改 nums
# 返回值是 None，不会返回新数组
nums.sort()
print(nums) # [1, 2, 3]4.2 sorted(nums)
python
nums = [3, 1, 2]
# sorted(nums) 会返回一个新列表
# 原 nums 不会被修改
new_nums = sorted(nums)
print(nums) # [3, 1, 2]
print(new_nums) # [1, 2, 3]4.3 降序排序
python
nums = [3, 1, 2]
# reverse=True 表示从大到小排序
nums.sort(reverse=True)
print(nums) # [3, 2, 1]4.4 按自定义规则排序
python
students = [
('Tom', 90),
('Jack', 80),
('Alice', 95)
]
# key=lambda x: x[1] 表示按照元组第二个元素排序
# 这里就是按成绩排序
students.sort(key=lambda x: x[1])
print(students) # [('Jack', 80), ('Tom', 90), ('Alice', 95)]4.5 多关键字排序
python
students = [
('Tom', 90),
('Jack', 90),
('Alice', 95)
]
# 先按成绩升序，再按名字升序
students.sort(key=lambda x: (x[1], x[0]))
print(students)4.6 Python 内置排序复杂度
text
时间复杂度：O(n log n)
最好情况：O(n)，当数据已经有很多有序片段时
空间复杂度：O(n)
稳定性：稳定Python 内置排序底层是 Timsort，它结合了归并排序和插入排序的思想，对真实数据中常见的“部分有序”情况很友好。
5. 冒泡排序 Bubble Sort
5.1 核心思想
冒泡排序的思想：
text
相邻两个元素比较。
如果前面的比后面的大，就交换。
每一轮会把当前最大的元素“冒泡”到数组末尾。比如：
python
nums = [5, 2, 3, 1]第一轮：
text
5 和 2 比，5 大，交换：[2, 5, 3, 1]
5 和 3 比，5 大，交换：[2, 3, 5, 1]
5 和 1 比，5 大，交换：[2, 3, 1, 5]第一轮结束，最大值 5 到了最后。
5.2 标准代码：升序冒泡排序
python
def bubble_sort(nums):
# n 是数组长度
n = len(nums)
# 外层循环控制轮数
# 最多需要 n - 1 轮
for i in range(n - 1):
# 内层循环负责相邻元素比较
# 每一轮结束后，最后 i 个元素已经排好
# 所以只需要比较到 n - 1 - i
for j in range(n - 1 - i):
# 如果前面的元素比后面的大，说明顺序错了
if nums[j] > nums[j + 1]:
# 交换两个相邻元素
nums[j], nums[j + 1] = nums[j + 1], nums[j]
# 返回排序后的数组
return nums测试：
python
nums = [5, 2, 3, 1]
print(bubble_sort(nums)) # [1, 2, 3, 5]5.3 优化版冒泡排序
如果某一轮没有发生交换，说明数组已经有序，可以提前结束。
python
def bubble_sort_optimized(nums):
# n 是数组长度
n = len(nums)
# 外层循环控制轮数
for i in range(n - 1):
# swapped 记录本轮是否发生交换
swapped = False
# 相邻元素比较
for j in range(n - 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 nums5.4 复杂度
text
最好时间复杂度：O(n)，优化版且数组本来有序
平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定5.5 易错点
- 内层循环是
range(n - 1 - i)。 - 升序排序条件是
nums[j] > nums[j + 1]。 - 降序排序条件是
nums[j] < nums[j + 1]。 - 冒泡排序适合入门，不适合做大数据最优解。
6. 选择排序 Selection Sort
6.1 核心思想
选择排序的思想：
text
每一轮从未排序部分找出最小值。
把最小值放到当前应该放的位置。比如：
python
[5, 2, 3, 1]第一轮从整个数组找最小值 1，放到第 0 位。
6.2 标准代码
python
def selection_sort(nums):
# n 是数组长度
n = len(nums)
# i 表示当前要放置最小值的位置
for i in range(n):
# min_index 记录当前未排序区间中最小元素的下标
min_index = i
# 从 i + 1 开始找更小的元素
for j in range(i + 1, n):
# 如果发现更小的元素，就更新 min_index
if nums[j] < nums[min_index]:
min_index = j
# 把最小元素交换到位置 i
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums6.3 复杂度
text
最好时间复杂度：O(n²)
平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定选择排序无论数组是否有序，都要找最小值，所以最好情况也是 O(n²)。
6.4 为什么不稳定
例如：
text
[2a, 2b, 1]第一轮最小值是 1，它会和 2a 交换：
text
[1, 2b, 2a]2a 和 2b 的相对顺序变了，所以选择排序不稳定。
7. 插入排序 Insertion Sort
7.1 核心思想
插入排序像打扑克牌：
text
左边是已经排好序的牌。
每次拿一张新牌，插入到左边合适位置。7.2 标准代码
python
def insertion_sort(nums):
# 从下标 1 开始
# 因为下标 0 可以看作已经有序
for i in range(1, len(nums)):
# cur 是当前要插入的元素
cur = nums[i]
# j 指向已排序部分的最后一个位置
j = i - 1
# 如果前面的元素比 cur 大，就往后移动
while j >= 0 and nums[j] > cur:
# 把 nums[j] 向后挪一位
nums[j + 1] = nums[j]
# j 继续向左找插入位置
j -= 1
# 循环结束后，j + 1 就是 cur 应该插入的位置
nums[j + 1] = cur
return nums7.3 复杂度
text
最好时间复杂度：O(n)，数组本来有序
平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)，数组逆序
空间复杂度：O(1)
稳定性：稳定7.4 适用场景
插入排序适合：
text
1. 数组规模小
2. 数组基本有序
3. 作为高级排序的小数组优化8. 希尔排序 Shell Sort
8.1 核心思想
希尔排序是插入排序的改进版。
普通插入排序一次只能挪一位。希尔排序先用较大的间隔 gap 分组，让元素更快接近最终位置，再逐渐缩小 gap。
过程：
text
gap = n // 2
按 gap 分组做插入排序
gap 继续减半
直到 gap = 1，最后做普通插入排序8.2 标准代码
python
def shell_sort(nums):
# n 是数组长度
n = len(nums)
# 初始间隔
gap = n // 2
# gap 不断缩小，直到变成 0
while gap > 0:
# 从 gap 开始，对每个分组做插入排序
for i in range(gap, n):
# cur 是当前要插入的元素
cur = nums[i]
# j 是当前元素的位置
j = i
# 在同一个 gap 分组内做插入排序
while j >= gap and nums[j - gap] > cur:
# 把前面较大的元素向后移动 gap 位
nums[j] = nums[j - gap]
# j 向前移动 gap
j -= gap
# 把 cur 放到正确位置
nums[j] = cur
# 缩小 gap
gap //= 2
return nums8.3 复杂度
希尔排序复杂度和 gap 序列有关。
通常记：
text
平均时间复杂度：约 O(n^1.3) 到 O(n²)
最坏时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定8.4 面试掌握程度
希尔排序不是高频手写题。知道它是插入排序的改进版，理解 gap 分组即可。
9. 归并排序 Merge Sort
9.1 核心思想
归并排序是典型分治算法。
text
分：把数组不断分成两半
治：分别排序左右两半
合：把两个有序数组合并成一个有序数组比如：
text
[5, 2, 3, 1]
拆分：
[5, 2] [3, 1]
[5] [2] [3] [1]
合并：
[2, 5] [1, 3]
最终合并：
[1, 2, 3, 5]9.2 递归返回新数组版
这个版本最容易理解。
python
def merge_sort(nums):
# 长度小于等于 1，本身就是有序的
if len(nums) <= 1:
return nums
# mid 是中间位置
mid = len(nums) // 2
# 递归排序左半部分
left = merge_sort(nums[:mid])
# 递归排序右半部分
right = merge_sort(nums[mid:])
# 合并两个有序数组
return merge(left, right)
def merge(left, right):
# ans 保存合并结果
ans = []
# i 指向 left 当前元素
i = 0
# j 指向 right 当前元素
j = 0
# 两个数组都还有元素时，比较谁更小
while i < len(left) and j < len(right):
# 相等时先放 left，可以保证稳定性
if left[i] <= right[j]:
ans.append(left[i])
i += 1
else:
ans.append(right[j])
j += 1
# left 如果有剩余，直接接到结果后面
while i < len(left):
ans.append(left[i])
i += 1
# right 如果有剩余，直接接到结果后面
while j < len(right):
ans.append(right[j])
j += 1
return ans9.3 原数组修改版
这个版本更接近刷题写法。
python
def merge_sort_in_place(nums):
# temp 是辅助数组，用于合并时临时存放元素
temp = [0] * len(nums)
def sort(left, right):
# 区间为空或只有一个元素时，不需要排序
if left >= right:
return
# 计算中点
mid = (left + right) // 2
# 排序左半区间
sort(left, mid)
# 排序右半区间
sort(mid + 1, right)
# 合并两个有序区间
merge(left, mid, right)
def merge(left, mid, right):
# i 指向左半区间起点
i = left
# j 指向右半区间起点
j = mid + 1
# k 指向 temp 当前写入位置
k = left
# 比较左右两个有序区间
while i <= mid and j <= right:
if nums[i] <= nums[j]:
temp[k] = nums[i]
i += 1
else:
temp[k] = nums[j]
j += 1
k += 1
# 左半区间如果还有剩余，继续写入
while i <= mid:
temp[k] = nums[i]
i += 1
k += 1
# 右半区间如果还有剩余，继续写入
while j <= right:
temp[k] = nums[j]
j += 1
k += 1
# 把 temp 中的有序结果复制回 nums
for p in range(left, right + 1):
nums[p] = temp[p]
# 对整个数组排序
sort(0, len(nums) - 1)
return nums9.4 复杂度
text
时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定为什么是 O(n log n)：
text
每层合并都要处理 n 个元素。
总共有 log n 层。
所以是 O(n log n)。9.5 适用场景
归并排序适合：
text
1. 要求稳定排序
2. 链表排序
3. 外部排序，大文件排序
4. 求逆序对10. 快速排序 Quick Sort
10.1 核心思想
快速排序也是分治。
text
选择一个基准值 pivot。
把小于 pivot 的放左边。
把大于 pivot 的放右边。
再递归排序左右区间。10.2 简单版快排：容易理解但空间不优
python
def quick_sort_simple(nums):
# 长度小于等于 1，本身有序
if len(nums) <= 1:
return nums
# 选第一个元素作为基准值
pivot = nums[0]
# small 保存小于 pivot 的元素
small = []
# equal 保存等于 pivot 的元素
equal = []
# large 保存大于 pivot 的元素
large = []
# 遍历数组，把元素分到三个列表
for num in nums:
if num < pivot:
small.append(num)
elif num > pivot:
large.append(num)
else:
equal.append(num)
# 递归排序 small 和 large，再拼接
return quick_sort_simple(small) + equal + quick_sort_simple(large)这个版本好理解，但用了额外列表，不是原地排序。
10.3 原地快排：Lomuto 分区
python
def quick_sort(nums):
def sort(left, right):
# 区间为空或只有一个元素，不需要排序
if left >= right:
return
# partition 会把数组分区，并返回 pivot 最终位置
pivot_index = partition(left, right)
# 递归排序 pivot 左边
sort(left, pivot_index - 1)
# 递归排序 pivot 右边
sort(pivot_index + 1, right)
def partition(left, right):
# 选择最右边元素作为 pivot
pivot = nums[right]
# i 表示小于等于 pivot 区间的最后一个位置
i = left - 1
# j 扫描 left 到 right - 1
for j in range(left, right):
# 如果 nums[j] 小于等于 pivot，就放到左边
if nums[j] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
# 把 pivot 放到正确位置
nums[i + 1], nums[right] = nums[right], nums[i + 1]
# 返回 pivot 最终位置
return i + 1
# 对整个数组排序
sort(0, len(nums) - 1)
return nums10.4 随机快排
固定选择最左或最右作为 pivot，遇到有序数组可能退化到 O(n²)。随机 pivot 可以降低退化概率。
python
import random
def quick_sort_random(nums):
def sort(left, right):
# 区间为空或只有一个元素，不需要排序
if left >= right:
return
# 分区并获取 pivot 最终位置
pivot_index = partition(left, right)
# 递归排序左右两边
sort(left, pivot_index - 1)
sort(pivot_index + 1, right)
def partition(left, right):
# 随机选择 pivot 下标
random_index = random.randint(left, right)
# 把随机 pivot 换到 right 位置
nums[random_index], nums[right] = nums[right], nums[random_index]
# 后面和普通 Lomuto 分区一样
pivot = nums[right]
i = left - 1
for j in range(left, right):
if nums[j] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[right] = nums[right], nums[i + 1]
return i + 1
sort(0, len(nums) - 1)
return nums10.5 三路快排：适合大量重复元素
三路快排把数组分为三段：
text
小于 pivot
等于 pivot
大于 pivot
python
import random
def quick_sort_three_way(nums):
def sort(left, right):
# 区间为空或只有一个元素，不需要排序
if left >= right:
return
# 随机选择 pivot，降低退化概率
random_index = random.randint(left, right)
nums[left], nums[random_index] = nums[random_index], nums[left]
# pivot 是基准值
pivot = nums[left]
# lt 表示小于 pivot 区间的右边界
lt = left
# gt 表示大于 pivot 区间的左边界
gt = right
# i 是当前扫描位置
i = left + 1
# 维护三个区域：
# nums[left+1 : lt+1] < pivot
# nums[lt+1 : i] == pivot
# nums[gt+1 : right+1] > pivot
while i <= gt:
if nums[i] < pivot:
# 当前元素小于 pivot，放到小于区间
nums[lt + 1], nums[i] = nums[i], nums[lt + 1]
lt += 1
i += 1
elif nums[i] > pivot:
# 当前元素大于 pivot，放到大于区间
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
# 注意：这里 i 不加 1
# 因为换过来的 nums[i] 还没判断过
else:
# 当前元素等于 pivot，直接跳过
i += 1
# 把 pivot 放到等于区间最前面
nums[left], nums[lt] = nums[lt], nums[left]
# 递归排序小于 pivot 的部分
sort(left, lt - 1)
# 递归排序大于 pivot 的部分
sort(gt + 1, right)
sort(0, len(nums) - 1)
return nums10.6 快排复杂度
text
平均时间复杂度：O(n log n)
最坏时间复杂度：O(n²)
平均空间复杂度：O(log n)，递归栈
最坏空间复杂度：O(n)
稳定性：不稳定10.7 快排易错点
- 分区边界容易错。
- pivot 最终位置要返回正确。
- 有序数组固定 pivot 容易退化。
- 有大量重复元素时，三路快排更好。
- 快排通常不稳定。
11. 堆排序 Heap Sort
11.1 堆是什么
堆是一种特殊的完全二叉树。
常见两种：
text
大根堆：每个节点都大于等于它的孩子
小根堆：每个节点都小于等于它的孩子数组表示堆时，对于下标 i：
text
左孩子：2 * i + 1
右孩子：2 * i + 2
父节点：(i - 1) // 211.2 堆排序思想
升序排序一般用大根堆。
步骤：
text
1. 把数组建成大根堆
2. 堆顶是最大值
3. 把堆顶和数组末尾交换
4. 缩小堆大小
5. 重新调整堆
6. 重复直到完成排序11.3 标准代码
python
def heap_sort(nums):
# n 是数组长度
n = len(nums)
def heapify(heap_size, root):
# largest 记录当前 root、左孩子、右孩子中最大值的位置
largest = root
# 左孩子下标
left = 2 * root + 1
# 右孩子下标
right = 2 * root + 2
# 如果左孩子存在，并且比当前 largest 更大
if left < heap_size and nums[left] > nums[largest]:
largest = left
# 如果右孩子存在，并且比当前 largest 更大
if right < heap_size and nums[right] > nums[largest]:
largest = right
# 如果最大值不是 root，说明需要交换
if largest != root:
nums[root], nums[largest] = nums[largest], nums[root]
# 交换后，largest 位置的子树可能不满足堆性质
# 所以继续向下调整
heapify(heap_size, largest)
# 第一步：建立大根堆
# 从最后一个非叶子节点开始向前调整
for i in range(n // 2 - 1, -1, -1):
heapify(n, i)
# 第二步：不断把堆顶最大值放到数组末尾
for end in range(n - 1, 0, -1):
# 把最大值 nums[0] 交换到当前末尾 end
nums[0], nums[end] = nums[end], nums[0]
# 堆大小减少 1，重新调整堆顶
heapify(end, 0)
return nums11.4 复杂度
text
建堆：O(n)
每次取最大值并调整：O(log n)，执行 n 次
总时间复杂度：O(n log n)
空间复杂度：O(1)，递归实现有 O(log n) 调用栈
稳定性：不稳定11.5 Python heapq
Python 的 heapq 默认是小根堆。
python
import heapq
nums = [5, 2, 3, 1]
# 原地建成小根堆
heapq.heapify(nums)
# 每次弹出最小值
while nums:
print(heapq.heappop(nums))大根堆可以取负数：
python
import heapq
nums = [5, 2, 3, 1]
# 取负后建小根堆，相当于原数字的大根堆
heap = [-x for x in nums]
heapq.heapify(heap)
while heap:
print(-heapq.heappop(heap))12. 计数排序 Counting Sort
12.1 核心思想
计数排序不比较大小，而是统计每个数字出现了几次。
适用前提：
text
数字是整数
数字范围不大比如：
python
nums = [3, 1, 2, 3, 1]统计：
text
1 出现 2 次
2 出现 1 次
3 出现 2 次再按顺序写回：
python
[1, 1, 2, 3, 3]12.2 简单版计数排序：非负整数
python
def counting_sort(nums):
# 空数组直接返回
if not nums:
return nums
# 找最大值，用来确定计数数组大小
max_num = max(nums)
# count[i] 表示数字 i 出现了几次
count = [0] * (max_num + 1)
# 统计每个数字出现次数
for num in nums:
count[num] += 1
# index 表示 nums 当前要写入的位置
index = 0
# 按数字从小到大，把数字写回 nums
for num in range(len(count)):
# 数字 num 出现 count[num] 次
for _ in range(count[num]):
nums[index] = num
index += 1
return nums12.3 支持负数的计数排序
python
def counting_sort_with_negative(nums):
# 空数组直接返回
if not nums:
return nums
# 找最小值和最大值
min_num = min(nums)
max_num = max(nums)
# 数字范围大小
range_size = max_num - min_num + 1
# count[i] 表示数字 i + min_num 出现次数
count = [0] * range_size
# 统计次数
for num in nums:
# num - min_num 是偏移后的下标
count[num - min_num] += 1
# 写回原数组
index = 0
for i in range(range_size):
# 还原真实数字
real_num = i + min_num
# 写入对应次数
for _ in range(count[i]):
nums[index] = real_num
index += 1
return nums12.4 复杂度
设：
text
n 是元素数量
k 是数值范围大小复杂度：
text
时间复杂度：O(n + k)
空间复杂度：O(k)
稳定性：可稳定不适合：
text
数字范围很大，比如 1 到 10^913. 桶排序 Bucket Sort
13.1 核心思想
桶排序的思想：
text
把数据分到多个桶里。
每个桶内部排序。
最后按桶顺序拼接。适合数据分布比较均匀的场景。
13.2 示例代码：排序 [0, 1) 范围小数
python
def bucket_sort(nums):
# 空数组直接返回
if not nums:
return nums
# n 个元素，创建 n 个桶
n = len(nums)
buckets = [[] for _ in range(n)]
# 把每个数字放进对应桶
for num in nums:
# num 在 [0, 1) 之间
# int(num * n) 可以得到桶下标
index = int(num * n)
# 防止 num 恰好等于 1 的边界情况
if index == n:
index = n - 1
# 放入对应桶
buckets[index].append(num)
# 每个桶内部排序
for bucket in buckets:
bucket.sort()
# 把所有桶按顺序拼接
result = []
for bucket in buckets:
result.extend(bucket)
return result13.3 复杂度
text
平均时间复杂度：O(n + k)
最坏时间复杂度：O(n²)，如果所有元素都落到一个桶
空间复杂度：O(n + k)
稳定性：取决于桶内排序是否稳定14. 基数排序 Radix Sort
14.1 核心思想
基数排序按位排序。
比如数字：
text
170, 45, 75, 90, 802, 24, 2, 66先按个位排序，再按十位排序，再按百位排序。
每一位排序必须是稳定排序。
14.2 非负整数基数排序
python
def radix_sort(nums):
# 空数组直接返回
if not nums:
return nums
# 找最大值，决定需要处理多少位
max_num = max(nums)
# exp 表示当前处理的位
# exp = 1 表示个位
# exp = 10 表示十位
# exp = 100 表示百位
exp = 1
# 只要 max_num 还有当前位，就继续
while max_num // exp > 0:
# 按当前位进行稳定计数排序
counting_sort_by_digit(nums, exp)
# 处理下一位
exp *= 10
return nums
def counting_sort_by_digit(nums, exp):
# output 保存按当前位排序后的结果
output = [0] * len(nums)
# 十进制每一位只有 0 到 9
count = [0] * 10
# 统计当前位数字出现次数
for num in nums:
# digit 是 num 在 exp 位上的数字
digit = (num // exp) % 10
count[digit] += 1
# 前缀和，用于确定最终位置
for i in range(1, 10):
count[i] += count[i - 1]
# 从右往左遍历，保证稳定性
for i in range(len(nums) - 1, -1, -1):
num = nums[i]
# 当前位数字
digit = (num // exp) % 10
# 当前数字应该放的位置
position = count[digit] - 1
# 放入 output
output[position] = num
# 更新该 digit 的位置
count[digit] -= 1
# 把 output 拷贝回 nums
for i in range(len(nums)):
nums[i] = output[i]14.3 复杂度
设：
text
n 是元素数量
d 是最大数字位数
k 是每一位的取值范围，十进制中 k = 10复杂度：
text
时间复杂度：O(d × (n + k))
空间复杂度：O(n + k)
稳定性：稳定15. 各排序算法怎么选
15.1 普通刷题
不是专门考排序实现时，直接：
python
nums.sort()15.2 要求稳定排序
考虑：
text
归并排序
插入排序
Python sort15.3 链表排序
优先考虑：
text
归并排序因为链表不适合随机访问。
15.4 Top K 问题
考虑：
text
堆
快速选择15.5 数字范围小
考虑：
text
计数排序15.6 数据分布均匀
考虑：
text
桶排序16. LeetCode 排序常见用法
16.1 排序 + 双指针
典型题：
text
15. 三数之和
16. 最接近的三数之和
18. 四数之和常见套路：
text
先排序
固定一个数
用左右双指针找剩下的数
跳过重复16.2 排序 + 贪心
典型题：
text
455. 分发饼干
435. 无重叠区间
452. 用最少数量的箭引爆气球
406. 根据身高重建队列排序后经常可以让问题出现明显的贪心顺序。
16.3 排序 + 区间合并
典型题：
text
56. 合并区间
57. 插入区间
986. 区间列表的交集区间题通常先按左端点排序。
17. 面试表达模板
17.1 快速排序表达
text
快速排序使用分治思想。
每次选择一个基准值 pivot，把数组分成小于 pivot 和大于 pivot 的两部分。
然后递归排序左右区间。
平均时间复杂度是 O(n log n)，最坏 O(n²)。
可以通过随机选择 pivot 降低退化概率。
快速排序通常是原地排序，但不稳定。17.2 归并排序表达
text
归并排序也是分治算法。
先把数组不断拆成两半，分别排序后，再合并两个有序数组。
每一层合并需要 O(n)，总共有 O(log n) 层，所以时间复杂度是 O(n log n)。
归并排序需要 O(n) 额外空间，是稳定排序。17.3 堆排序表达
text
堆排序利用大根堆。
先把数组建成大根堆，堆顶是最大值。
然后不断把堆顶和末尾交换，并缩小堆范围，再调整堆。
时间复杂度稳定是 O(n log n)，空间复杂度 O(1)，但排序不稳定。17.4 冒泡排序表达
text
冒泡排序每轮比较相邻元素，如果顺序错误就交换。
每一轮可以把当前最大元素放到末尾。
时间复杂度 O(n²)，空间复杂度 O(1)，是稳定排序。17.5 插入排序表达
text
插入排序把数组分为已排序区间和未排序区间。
每次从未排序区间取一个元素，插入到已排序区间的合适位置。
数组基本有序时效率很好，最好 O(n)，平均和最坏 O(n²)，稳定且原地。18. 快速复习版
18.1 必背复杂度
text
冒泡排序：O(n²)，稳定，原地
选择排序：O(n²)，不稳定，原地
插入排序：O(n²)，稳定，原地，基本有序时快
希尔排序：插入排序改进版，不稳定
归并排序：O(n log n)，稳定，O(n) 空间
快速排序：平均 O(n log n)，最坏 O(n²)，不稳定，原地
堆排序：O(n log n)，不稳定，原地
计数排序：O(n + k)，适合范围小的整数
桶排序：平均 O(n + k)，适合均匀分布
基数排序：O(d × (n + k))，适合整数或字符串
Python sort：O(n log n)，稳定18.2 学习顺序建议
text
1. 冒泡排序：理解相邻交换
2. 选择排序：理解选择最小值
3. 插入排序：理解有序区间
4. 归并排序：理解分治和合并
5. 快速排序：理解 pivot 和 partition
6. 堆排序：理解堆和下沉调整
7. 计数 / 桶 / 基数排序：理解非比较排序场景18.3 刷题口诀
text
不是考排序实现，直接 nums.sort()
排序后常配双指针
排序后方便去重
排序后常用于贪心
区间题通常先按左端点排序
Top K 优先想堆或快选
链表排序优先想归并19. 自测题
- 冒泡排序为什么稳定？
- 选择排序为什么不稳定？
- 插入排序为什么适合基本有序数组？
- 归并排序为什么时间复杂度是 O(n log n)？
- 快速排序为什么最坏会退化成 O(n²)？
- 快排怎么避免最坏情况？
- 堆排序为什么不稳定？
- 计数排序什么时候比快排更快？
- 桶排序为什么要求数据分布比较均匀？
- Python 的
sort()和sorted()有什么区别？
20. 最终总结
排序算法不是只背代码，重点是理解：
text
1. 它怎么比较或组织数据
2. 每一轮在干什么
3. 为什么能排好
4. 时间复杂度为什么是这样
5. 是否稳定
6. 是否原地
7. 什么场景适合对 LeetCode 来说，最常用的是：
python
nums.sort()但为了面试基本功，至少要能手写并讲清：
text
冒泡排序
选择排序
插入排序
归并排序
快速排序
堆排序真正刷题时，排序更多是工具。更重要的是排序之后怎么配合：
text
双指针
贪心
区间合并
去重
二分
堆