排序算法完全指南¶
重要性：⭐⭐⭐⭐⭐ 学习时间：1-2周 前置知识：数组、复杂度分析
📚 目录¶
排序算法总览¶
算法对比表¶
| 算法 | 平均时间 | 最坏时间 | 最好时间 | 空间 | 稳定 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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(n1.25)~O(n1.5) | O(n²) | O(n log n) | O(1) | ❌ | 中等规模 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | 大数据、外排 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌ | 通用排序 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | 空间受限 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ | 整数、范围小 |
| 桶排序 | O(n+k) | O(n²) | O(n) | O(n+k) | ✅ | 均匀分布 |
| 基数排序 | O(d×n) | O(d×n) | O(d×n) | O(n+k) | ✅ | 整数、固定位数 |
什么是稳定性？¶
稳定排序：相等元素的相对顺序保持不变
示例：
Text Only
原始: [(3, A), (1, B), (3, C), (2, D)]
稳定排序后: [(1, B), (2, D), (3, A), (3, C)]
↑ ↑
A在C前（保持原顺序）
不稳定排序后: [(1, B), (2, D), (3, C), (3, A)]
↑ ↑
C在A前（顺序改变）
初级排序算法¶
1️⃣ 冒泡排序（Bubble Sort）¶
算法思想¶
像气泡一样，每次将最大的元素"冒"到末尾。
Python实现¶
Python
def bubble_sort(arr):
"""
冒泡排序
时间：O(n²)
空间：O(1)
稳定：✅
"""
n = len(arr)
for i in range(n):
# 优化：标记本轮是否有交换
swapped = False
for j in range(n - 1 - i):
# 相邻元素比较
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 如果没有交换，说明已经有序
if not swapped:
break
return arr
# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
print("排序后:", bubble_sort(arr.copy()))
算法图解¶
Text Only
初始: [64, 34, 25, 12, 22, 11, 90]
第1轮:
[64, 34, 25, 12, 22, 11, 90]
↓比较 ↓
[34, 64, 25, 12, 22, 11, 90]
↓比较 ↓
[34, 25, 64, 12, 22, 11, 90]
↓比较 ↓
[34, 25, 12, 64, 22, 11, 90]
↓比较 ↓
[34, 25, 12, 22, 64, 11, 90]
↓比较 ↓
[34, 25, 12, 22, 11, 64, 90]
↓比较 ↓
[34, 25, 12, 22, 11, 64, 90]
✓ 90已到位
第2轮:
[34, 25, 12, 22, 11, 64, 90]
↓比较 ↓
[25, 34, 12, 22, 11, 64, 90]
↓比较 ↓
[25, 12, 34, 22, 11, 64, 90]
↓比较 ↓
[25, 12, 22, 34, 11, 64, 90]
↓比较 ↓
[25, 12, 22, 11, 34, 64, 90]
↓比较 ↓
[25, 12, 22, 11, 34, 64, 90]
✓ 64已到位
...持续n-1轮
最终: [11, 12, 22, 25, 34, 64, 90]
复杂度分析¶
- 最好情况：O(n) - 已经有序，只需一轮遍历
- 最坏情况：O(n²) - 逆序
- 平均情况：O(n²)
2️⃣ 选择排序（Selection Sort）¶
算法思想¶
每次从未排序部分选择最小的元素，放到已排序部分的末尾。
Python实现¶
Python
def selection_sort(arr):
"""
选择排序
时间：O(n²)
空间：O(1)
稳定：❌
"""
n = len(arr)
for i in range(n):
# 找到未排序部分的最小值
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 交换到正确位置
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 测试
arr = [64, 25, 12, 22, 11]
print("排序前:", arr)
print("排序后:", selection_sort(arr.copy()))
算法图解¶
Text Only
初始: [64, 25, 12, 22, 11]
↑
已排序部分为空
第1轮: 找最小值11
[64, 25, 12, 22, 11]
↓ ↓ ↓ ↓ ↓
比较所有元素，11最小
交换64和11
[11, 25, 12, 22, 64]
↑
已排序
第2轮: 找最小值12
[11, 25, 12, 22, 64]
↑ ↑ ↑
未排序部分找最小
交换25和12
[11, 12, 25, 22, 64]
↑
已排序
第3轮: 找最小值22
[11, 12, 25, 22, 64]
↑ ↑
交换25和22
[11, 12, 22, 25, 64]
↑
已排序
第4轮: 找最小值25
[11, 12, 22, 25, 64]
↑
25已经是最小
最终: [11, 12, 22, 25, 64]
3️⃣ 插入排序（Insertion Sort）¶
算法思想¶
像整理扑克牌一样，将每个元素插入到已排序部分的正确位置。
Python实现¶
Python
def insertion_sort(arr):
"""
插入排序
时间：O(n²)
空间：O(1)
稳定：✅
适合：小数据、近似有序的数据
"""
n = len(arr)
for i in range(1, n):
# 当前要插入的元素
key = arr[i]
j = i - 1
# 将大于key的元素向后移
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# 插入到正确位置
arr[j + 1] = key
return arr
# 测试
arr = [12, 11, 13, 5, 6]
print("排序前:", arr)
print("排序后:", insertion_sort(arr.copy()))
算法图解¶
Text Only
初始: [12, 11, 13, 5, 6]
↑
已排序
第1轮: 插入11
[12, 11, 13, 5, 6]
↓ ↓
比较: 11 < 12
后移: [12, 12, 13, 5, 6]
插入: [11, 12, 13, 5, 6]
↑
已排序
第2轮: 插入13
[11, 12, 13, 5, 6]
↓
比较: 13 > 12，无需移动
[11, 12, 13, 5, 6]
↑
已排序
第3轮: 插入5
[11, 12, 13, 5, 6]
↓ ↓ ↓ ↓
比较并后移: 5 < 13, 5 < 12, 5 < 11
[11, 11, 12, 13, 6]
[5, 11, 12, 13, 6]
插入: [5, 11, 12, 13, 6]
↑
已排序
第4轮: 插入6
[5, 11, 12, 13, 6]
↓ ↓ ↓ ↓ ↓
比较并后移: 6 < 13, 6 < 12, 6 < 11
[5, 6, 11, 12, 13]
↑
已排序
最终: [5, 6, 11, 12, 13]
优化：二分插入排序¶
Python
def binary_insertion_sort(arr):
"""
二分插入排序
优化：用二分查找找到插入位置
时间：O(n²)（虽然查找是O(log n)，但移动还是O(n)）
"""
for i in range(1, len(arr)):
key = arr[i]
# 二分查找插入位置
left, right = 0, i
while left < right:
mid = (left + right) // 2
if arr[mid] < key:
left = mid + 1
else:
right = mid
# 移动元素
for j in range(i, left, -1):
arr[j] = arr[j - 1]
# 插入
arr[left] = key
return arr
4️⃣ 希尔排序（Shell Sort）¶
算法思想¶
插入排序的改进版，通过比较相距一定间隔的元素来工作。
Python实现¶
Python
def shell_sort(arr):
"""
希尔排序
时间：O(n^1.25)~O(n^1.5) 平均（取决于间隔序列）
空间：O(1)
稳定：❌
间隔序列：n/2, n/4, n/8, ..., 1
"""
n = len(arr)
gap = n // 2
while gap > 0:
# 对每个间隔序列进行插入排序
for i in range(gap, n):
temp = arr[i]
j = i
# 插入排序（间隔为gap）
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
# 测试
arr = [12, 34, 54, 2, 3]
print("排序前:", arr)
print("排序后:", shell_sort(arr.copy()))
算法图解¶
Text Only
初始: [12, 34, 54, 2, 3], n=5
gap = 5//2 = 2
第1轮: gap=2
间隔为2的元素分组:
[12, __, 54, __, 3] → 索引0, 2, 4
[__ 34, __, 2, __] → 索引1, 3
组1排序: [12, 54, 3] → [3, 12, 54]
组2排序: [34, 2] → [2, 34]
合并: [3, 2, 12, 34, 54]
gap = 2//2 = 1
第2轮: gap=1（普通插入排序）
[3, 2, 12, 34, 54]
↓
[2, 3, 12, 34, 54]
gap = 1//2 = 0，结束
最终: [2, 3, 12, 34, 54]
间隔序列优化¶
Python
def shell_sort_optimized(arr):
"""
优化的Shell排序（Sedgewick间隔序列）
"""
n = len(arr)
gap = 1
# 生成初始间隔
while gap < n // 3:
gap = gap * 3 + 1 # 1, 4, 13, 40, 121, ...
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 3
return arr
高级排序算法¶
5️⃣ 归并排序（Merge Sort）¶
算法思想¶
分治策略： 1. 分：将数组从中间分成两部分 2. 治：递归排序两部分 3. 合：合并两个有序数组
Python实现¶
Python
def merge_sort(arr):
"""
归并排序
时间：O(n log n) 所有情况
空间：O(n)
稳定：✅
适合：大数据、外部排序
"""
if len(arr) <= 1:
return arr
# 分
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合
return merge(left, right)
def merge(left, right):
"""合并两个有序数组"""
result = []
i = j = 0
# 比较并合并
while i < len(left) and j < len(right):
if left[i] <= right[j]: # 保持稳定
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 添加剩余元素
result.extend(left[i:])
result.extend(right[j:])
return result
# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
print("排序前:", arr)
print("排序后:", merge_sort(arr))
算法图解¶
Text Only
初始: [38, 27, 43, 3, 9, 82, 10]
分解过程（递归）:
[38, 27, 43, 3, 9, 82, 10]
↓
[38, 27, 43] [3, 9, 82, 10]
↓ ↓
[38] [27, 43] [3, 9] [82, 10]
↓ ↓ ↓
[27] [43] [3] [9] [82] [10]
合并过程（递归返回）:
[27] + [43] = [27, 43]
[38] + [27, 43] = [27, 38, 43]
[3] + [9] = [3, 9]
[82] + [10] = [10, 82]
[3, 9] + [10, 82] = [3, 9, 10, 82]
[27, 38, 43] + [3, 9, 10, 82] = [3, 9, 10, 27, 38, 43, 82]
最终: [3, 9, 10, 27, 38, 43, 82]
原地归并排序¶
Python
def merge_sort_inplace(arr):
"""原地归并排序（节省空间）"""
if len(arr) <= 1:
return arr
n = len(arr)
temp = [0] * n
def merge_inplace(left, mid, right):
"""原地合并arr[left..mid]和arr[mid+1..right]"""
# 复制到临时数组
for i in range(left, right + 1):
temp[i] = arr[i]
i, j, k = left, mid + 1, left
while i <= mid and j <= right:
if temp[i] <= temp[j]:
arr[k] = temp[i]
i += 1
else:
arr[k] = temp[j]
j += 1
k += 1
while i <= mid:
arr[k] = temp[i]
i += 1
k += 1
def sort(left, right):
if left < right:
mid = (left + right) // 2
sort(left, mid)
sort(mid + 1, right)
merge_inplace(left, mid, right)
sort(0, n - 1)
return arr
6️⃣ 快速排序（Quick Sort）¶
算法思想¶
分治策略： 1. 选择一个基准值（pivot） 2. 将数组分为小于pivot和大于等于pivot两部分 3. 递归排序两部分
Python实现（多种方案）¶
Python
def quick_sort_simple(arr):
"""
快速排序 - 简洁版（易理解，但使用额外空间）
时间：O(n log n) 平均，O(n²) 最坏
空间：O(n)
稳定：❌
"""
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_simple(left) + middle + quick_sort_simple(right)
def quick_sort_inplace(arr, low=0, high=None):
"""
快速排序 - 原地版（面试推荐）
时间：O(n log n) 平均，O(n²) 最坏
空间：O(log n) - 递归栈
"""
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort_inplace(arr, low, pivot_idx - 1)
quick_sort_inplace(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
"""Lomuto分区方案"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort_optimized(arr, low=0, high=None):
"""
优化的快速排序
优化点：
1. 随机选择pivot（避免最坏情况）
2. 三数取中法
3. 小数组使用插入排序
"""
if high is None:
high = len(arr) - 1
# 小数组优化：使用插入排序
if high - low < 10:
insertion_sort_range(arr, low, high)
return arr
# 三数取中法选择pivot
mid = (low + high) // 2
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 将中值放到high-1位置
arr[mid], arr[high - 1] = arr[high - 1], arr[mid]
# 分区（使用三数取中后的pivot）
pivot_idx = partition_optimized(arr, low, high - 1, arr[high - 1])
quick_sort_optimized(arr, low, pivot_idx - 1)
quick_sort_optimized(arr, pivot_idx + 1, high)
return arr
def partition_optimized(arr, low, high, pivot):
"""优化版分区"""
i = low
j = high
while True:
while arr[i] < pivot:
i += 1
while arr[j] > pivot:
j -= 1
if i >= j:
return i
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
def insertion_sort_range(arr, low, high):
"""对指定范围进行插入排序"""
for i in range(low + 1, high + 1):
key = arr[i]
j = i - 1
while j >= low and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# 测试
arr = [10, 7, 8, 9, 1, 5]
print("排序前:", arr)
print("排序后:", quick_sort_optimized(arr.copy()))
算法图解¶
Text Only
初始: [10, 7, 8, 9, 1, 5]
选择pivot = 5 (最后一个元素)
分区过程:
[10, 7, 8, 9, 1, 5]
↓ ↓ ↓ ↓ ↓ pivot
i=-1
j=0: 10 > 5, 不交换
j=1: 7 > 5, 不交换
j=2: 8 > 5, 不交换
j=3: 9 > 5, 不交换
j=4: 1 < 5, i=0, 交换arr[0]和arr[4]
[1, 7, 8, 9, 10, 5]
↑ i ↑ j
j=5: 到达pivot，交换arr[i+1]和pivot
[1, 5, 8, 9, 10, 7]
↑ pivot
结果: 左=[1], 右=[8, 9, 10, 7]
递归排序左边[1]: 已排序 ✓
递归排序右边[8, 9, 10, 7]:
选择pivot=7
...
最终: [1, 5, 7, 8, 9, 10]
7️⃣ 堆排序（Heap Sort）¶
算法思想¶
利用二叉堆（完全二叉树）的性质： - 大顶堆：父节点 >= 子节点 - 小顶堆：父节点 <= 子节点
Python实现¶
Python
def heap_sort(arr):
"""
堆排序
时间：O(n log n) 所有情况
空间：O(1)
稳定：❌
适合：空间受限的场景
"""
n = len(arr)
# 1. 建立大顶堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 2. 逐个提取堆顶元素（最大值）
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 将最大值移到末尾
heapify(arr, i, 0) # 重新堆化
return arr
def heapify(arr, n, i):
"""
维护大顶堆性质
arr: 数组
n: 堆大小
i: 当前节点索引
"""
largest = i
left = 2 * i + 1 # 左子节点
right = 2 * i + 2 # 右子节点
# 找出最大值
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是当前节点，交换并递归
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
# 测试
arr = [12, 11, 13, 5, 6, 7]
print("排序前:", arr)
print("排序后:", heap_sort(arr.copy()))
算法图解¶
Text Only
初始数组: [12, 11, 13, 5, 6, 7]
步骤1: 建立大顶堆
数组表示（完全二叉树）:
12(0)
/ \
11(1) 13(2)
/ \ /
5(3)6(4)7(5)
堆化（从最后一个非叶子节点开始）:
i=2: 节点13，子节点7，13最大，无需调整
i=1: 节点11，子节点5和6，11最大，无需调整
i=0: 节点12，子节点11和13，13最大
交换12和13
13(0)
/ \
11(1) 12(2)
/ \ /
5(3)6(4)7(5)
堆化完成: [13, 11, 12, 5, 6, 7]
步骤2: 逐个提取最大值
第1次:
交换13和7: [7, 11, 12, 5, 6, 13]
堆化前5个元素
7
/ \
11 12
/ \
5 6
交换7和12（12最大）:
12
/ \
11 7
/ \
5 6
结果: [12, 11, 7, 5, 6, 13]
第2次:
交换12和6: [6, 11, 7, 5, 12, 13]
堆化前4个元素
6
/ \
11 7
/
5
交换6和11（11最大）:
11
/ \
6 7
/
5
结果: [11, 6, 7, 5, 12, 13]
...持续进行
最终: [5, 6, 7, 11, 12, 13]
特殊排序算法¶
8️⃣ 计数排序（Counting Sort）¶
算法思想¶
统计每个元素出现的次数，然后按顺序输出。
Python实现¶
Python
def counting_sort(arr):
"""
计数排序
时间：O(n + k)，k是数据范围
空间：O(k)
稳定：✅
适合：整数、范围小
"""
if not arr:
return arr
# 1. 找出最大值和最小值
max_val = max(arr)
min_val = min(arr)
range_of_elements = max_val - min_val + 1
# 2. 创建计数数组
count = [0] * range_of_elements
# 3. 统计每个元素的出现次数
for num in arr:
count[num - min_val] += 1
# 4. 重构排序后的数组
result = []
for i in range(range_of_elements):
result.extend([i + min_val] * count[i])
return result
# 测试
arr = [4, 2, 2, 8, 3, 3, 1]
print("排序前:", arr)
print("排序后:", counting_sort(arr))
# 输出: [1, 2, 2, 3, 3, 4, 8]
算法图解¶
Text Only
初始: [4, 2, 2, 8, 3, 3, 1]
范围: 1-8
步骤1: 统计频率
值: 1 2 3 4 5 6 7 8
次数:1 2 2 1 0 0 0 1
步骤2: 累积计数（可选，用于稳定排序）
值: 1 2 3 4 5 6 7 8
累积:1 3 5 6 6 6 6 7
步骤3: 输出
1出现1次 → [1]
2出现2次 → [1, 2, 2]
3出现2次 → [1, 2, 2, 3, 3]
4出现1次 → [1, 2, 2, 3, 3, 4]
...
8出现1次 → [1, 2, 2, 3, 3, 4, 8]
最终: [1, 2, 2, 3, 3, 4, 8]
9️⃣ 桶排序（Bucket Sort）¶
算法思想¶
将元素分到有限数量的桶中，每个桶单独排序，最后合并。
Python实现¶
Python
def bucket_sort(arr, bucket_size=5):
"""
桶排序
时间：O(n + k) 平均，O(n²) 最坏
空间：O(n + k)
稳定：✅
适合：均匀分布的数据
"""
if not arr:
return arr
# 1. 确定最小值和最大值
min_val, max_val = min(arr), max(arr)
# 2. 确定桶的数量
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
# 3. 将元素分配到桶中
for num in arr:
buckets[(num - min_val) // bucket_size].append(num)
# 4. 对每个桶进行排序
for bucket in buckets:
bucket.sort() # 使用内置排序
# 5. 合并所有桶
result = []
for bucket in buckets:
result.extend(bucket)
return result
# 测试
arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
print("排序前:", arr)
print("排序后:", bucket_sort(arr))
🔟 基数排序（Radix Sort）¶
算法思想¶
按照位数从低位到高位进行排序。
Python实现¶
Python
def radix_sort(arr):
"""
基数排序
时间：O(d × n)，d是最大位数
空间：O(n + k)
稳定：✅
适合：整数、固定位数
"""
if not arr:
return arr
# 1. 找出最大值，确定位数
max_val = max(arr)
# 2. 对每一位进行计数排序
exp = 1 # 当前位数（个位、十位、百位...）
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
"""根据指定位数进行计数排序"""
n = len(arr)
output = [0] * n
count = [0] * 10 # 0-9共10个数字
# 统计当前位数的频率
for num in arr:
index = (num // exp) % 10
count[index] += 1
# 累积计数
for i in range(1, 10):
count[i] += count[i - 1]
# 从后向前构建输出数组（保持稳定）
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
# 复制回原数组
for i in range(n):
arr[i] = output[i]
# 测试
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("排序前:", arr)
print("排序后:", radix_sort(arr.copy()))
# 输出: [2, 24, 45, 66, 75, 90, 170, 802]
算法图解¶
Text Only
初始: [170, 45, 75, 90, 802, 24, 2, 66]
第1轮: 个位数排序
170(0), 90(0), 802(2), 2(2), 24(4), 45(5), 75(5), 66(6)
→ [170, 90, 802, 2, 24, 45, 75, 66]
第2轮: 十位数排序
170(7), 802(0), 2(0), 24(2), 45(4), 75(7), 66(6), 90(9)
→ [802, 2, 24, 45, 66, 170, 75, 90]
第3轮: 百位数排序
802(8), 170(1), 75(0), 90(0), 66(0), 45(0), 24(0), 2(0)
→ [2, 24, 45, 66, 75, 90, 170, 802]
最终: [2, 24, 45, 66, 75, 90, 170, 802]
排序算法选择¶
决策树¶
Text Only
需要排序
↓
数据规模？
├── 小于10 → 插入排序
├── 10-100 → 希尔排序或快速排序
└── 大于100 → 快速排序或归并排序
↓
数据特征？
├── 近似有序 → 插入排序或Timsort
├── 随机分布 → 快速排序
├── 大量重复 → 三路快速排序
└── 整数且范围小 → 计数排序
↓
是否稳定？
├── 是 → 归并排序、插入排序、计数排序
└── 否 → 快速排序、堆排序、选择排序
↓
内存限制？
├── 严格 → 堆排序（O(1)空间）
└── 宽松 → 归并排序、快速排序
↓
最终选择
实际应用建议¶
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 通用排序 | 快速排序 | 平均性能最好 |
| 大数据 | 归并排序 | 稳定O(n log n) |
| 小数据 | 插入排序 | 简单高效 |
| 内存受限 | 堆排序 | O(1)空间 |
| 整数小范围 | 计数排序 | O(n)时间 |
| 外部排序 | 归并排序 | 适合文件 |
| 在线排序 | 插入排序 | 边来边排 |
| 并行排序 | 归并排序 | 易并行化 |
LeetCode题目¶
基础题¶
-
合并两个有序数组
Pythondef merge(nums1, m, nums2, n): """ LeetCode 88 合并两个有序数组到nums1 """ # 从后向前合并 p1, p2, p = m - 1, n - 1, m + n - 1 while p1 >= 0 and p2 >= 0: if nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 # 复制剩余元素 nums1[:p2 + 1] = nums2[:p2 + 1] # 切片操作：[start:end:step]提取子序列 -
颜色分类
Pythondef sort_colors(nums): """ LeetCode 75 荷兰国旗问题 """ low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: # nums[mid] == 2 nums[mid], nums[high] = nums[high], nums[mid] high -= 1 -
最大间距
中等题¶
-
排序链表
Pythondef sort_list(head): """ LeetCode 148 链表排序，要求O(n log n) """ if not head or not head.next: return head # 找中点 slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # 分割 mid = slow.next slow.next = None # 递归排序 left = sort_list(head) right = sort_list(mid) # 合并 return merge_two_lists(left, right) -
最小K个数
困难题¶
- 数组中的第K个最大元素 Python
def find_kth_largest(nums, k): """ LeetCode 215 """ # 方法1: 排序后取第k个 # return sorted(nums, reverse=True)[k - 1] # 方法2: 快速选择（期望O(n)） def quick_select(left, right, k): pivot_idx = partition(left, right) if pivot_idx == k: return nums[pivot_idx] elif pivot_idx < k: return quick_select(pivot_idx + 1, right, k) else: return quick_select(left, pivot_idx - 1, k) def partition(left, right): pivot = nums[right] i = left for j in range(left, right): if nums[j] <= pivot: nums[i], nums[j] = nums[j], nums[i] i += 1 nums[i], nums[right] = nums[right], nums[i] return i return quick_select(0, len(nums) - 1, len(nums) - k)
📝 总结¶
关键要点¶
✅ 排序算法分类： - 初级：冒泡、选择、插入 - 高级：归并、快速、堆 - 特殊：计数、桶、基数
✅ 核心思想： - 冒泡：相邻交换 - 选择：每次选最小 - 插入：边插入边排序 - 归并：分治合并 - 快速：分治分区 - 堆：利用堆性质
✅ 选择策略： - 通用：快速排序 - 稳定：归并排序 - 空间受限：堆排序 - 整数小范围：计数排序
下一步¶
继续学习： - 搜索算法 - 二分搜索、BFS、DFS