本文是《排序算法系列》第二篇。上一篇我们讲解了冒泡排序和插入排序这一篇我们聚焦选择排序和归并排序。前者以“交换次数少”著称后者则是分治思想的经典代表也是大数据排序的首选之一。选择排序Selection Sort1. 核心思想生活直觉想象你面前有一排打乱的扑克牌你要把它们从小到大排好。你的做法是先扫一遍所有牌找出最小的那张把它放到第一位然后从剩下的牌里再找出最小的放到第二位以此类推。选择排序正是如此每一轮从未排序区间中选出最小或最大的元素放到已排序区间的末尾。它不像冒泡那样频繁交换而是“先看准再动手”——一轮只交换一次。2. 详细执行步骤手把手模拟假设我们要对数组升序排列[5, 1, 4, 2, 8]初始状态整个数组都是未排序区。第 1 轮i 0目标把最小值放到下标 0假设最小值下标min_idx 0值为 5遍历未排序区遇到1下标 11 5更新min_idx 1遇到44 1否不动遇到22 1否不动遇到88 1否不动遍历结束最小值是1与下标 0 的5交换 →[1, 5, 4, 2, 8]已排序区[1]第 2 轮i 1目标把次小值放到下标 1假设min_idx 1值为 5遍历未排序区下标 2 到 4遇到44 5更新min_idx 2遇到22 4更新min_idx 3遇到88 2否不动最小值是2与下标 1 的5交换 →[1, 2, 4, 5, 8]已排序区[1, 2]第 3 轮i 2假设min_idx 2值为 4遍历未排序区下标 3 到 4遇到55 4否不动遇到88 4否不动最小值就是4无需交换 →[1, 2, 4, 5, 8]第 4 轮i 3假设min_idx 3值为 5遍历未排序区下标 4遇到88 5否不动最小值就是5无需交换排序完成3. 标准代码实现Pythondef selection_sort(arr): n len(arr) # 外层循环确定第 i 个位置应该放哪个元素 for i in range(n - 1): 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 arrJavapublic static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } int temp arr[i]; arr[i] arr[minIdx]; arr[minIdx] temp; } }Cvoid selectionSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } swap(arr[i], arr[minIdx]); } }4. 时间复杂度与空间复杂度硬核分析维度详情最坏时间复杂度O(n²) —— 无论数据如何比较次数固定为 n(n-1)/2最好时间复杂度O(n²) —— 即使数组已经有序仍需完整遍历找最小值平均时间复杂度O(n²)空间复杂度O(1) —— 原地排序只用几个临时变量稳定性不稳定—— 例如[5, 5, 1]第一轮将第一个 5 与 1 交换两个 5 的相对顺序被破坏关键特点选择排序的比较次数和交换次数是分离的。比较次数始终是 O(n²)但交换次数最多只有 n-1 次。这是它相对于冒泡排序的最大优势——当“交换”操作代价很高时比如元素是大型结构体选择排序反而更划算。5. 三大关键优化优化一二元选择排序同时找最大和最小每一轮同时找出最小值和最大值分别放到两端。这样外层循环次数减半比较次数虽仍是 O(n²)但常数因子减小。def selection_sort_bidirectional(arr): n len(arr) left, right 0, n - 1 while left right: min_idx, max_idx left, left for i in range(left, right 1): if arr[i] arr[min_idx]: min_idx i if arr[i] arr[max_idx]: max_idx i # 先交换最小值到左端 arr[left], arr[min_idx] arr[min_idx], arr[left] # 注意如果最大值原本在 left 位置交换后它跑到了 min_idx if max_idx left: max_idx min_idx arr[right], arr[max_idx] arr[max_idx], arr[right] left 1 right - 1 return arr优化二记录索引而非立即交换标准实现已经是这样做的——先遍历找最小值下标最后才交换一次。不要写成“发现更小就立即交换”那会退化成冒泡排序。优化三堆排序选择排序的终极进化选择排序的瓶颈在于“找最小值”需要 O(n) 遍历。如果用堆来维护未排序区找最小值只需 O(log n)整体复杂度降到 O(n log n)——这就是堆排序。可以说堆排序是选择排序思想的“质变版”。6. 与其他排序算法的对比算法平均时间复杂度交换次数是否稳定特点选择排序O(n²)最多 n-1 次不稳定交换少比较多冒泡排序O(n²)最多 n(n-1)/2 次稳定交换频繁插入排序O(n²)最多 n(n-1)/2 次移动稳定对部分有序极快堆排序O(n log n)O(n log n)不稳定选择排序的升级版一句话总结选择排序是“交换次数最少”的 O(n²) 算法适合交换代价高、数据量小的场景。7. 适用场景数据规模小n 50且交换操作代价高如元素为大型对象。对稳定性没有要求的场景。教学演示帮助理解“选择”与“交换”的分离。作为堆排序的入门铺垫。归并排序Merge Sort1. 核心思想生活直觉想象你手上有两叠已经按从小到大排好的扑克牌你要把它们合并成一叠有序的牌。你只需要比较两叠牌最上面的那张谁小就先拿谁重复这个过程即可。归并排序的核心就是分治Divide and Conquer分把数组从中间切成两半递归地对左右两半排序。治把两个已经有序的子数组合并成一个有序数组。就像把一个大问题拆成两个小问题解决后再把结果“拼”起来。2. 详细执行步骤手把手模拟假设我们要对数组升序排列[5, 1, 4, 2, 8]第一步分递归拆分[5, 1, 4, 2, 8]↓ 从中间切[5, 1] [4, 2, 8]↓ ↓[5] [1] [4] [2, 8]↓[2] [8]第二步治合并合并[5]和[1]→[1, 5]合并[2]和[8]→[2, 8]合并[4]和[2, 8]→[2, 4, 8]合并[1, 5]和[2, 4, 8]→[1, 2, 4, 5, 8]重点看最后一次合并[1, 5]和[2, 4, 8]步骤左指针右指针比较结果数组1121 2取 1[1]2525 2取 2[1, 2]3545 4取 4[1, 2, 4]4585 8取 5[1, 2, 4, 5]5空8左边空取 8[1, 2, 4, 5, 8]排序完成3. 标准代码实现Pythondef merge_sort(arr): 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 resultJavapublic static void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); // 递归左半 mergeSort(arr, mid 1, right); // 递归右半 merge(arr, left, mid, right); // 合并 } private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; System.arraycopy(temp, 0, arr, left, temp.length); }Cvoid merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } } void mergeSort(vectorint arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }4. 时间复杂度与空间复杂度硬核分析维度详情最坏时间复杂度O(n log n) —— 无论数据如何拆分深度为 log n每层合并 O(n)最好时间复杂度O(n log n) —— 即使已经有序仍需完整拆分和合并平均时间复杂度O(n log n)空间复杂度O(n)—— 合并时需要额外数组这是归并排序的最大缺点稳定性稳定—— 合并时用保证相等元素左边优先递归树分析n → 合并代价 O(n)/ \n/2 n/2 → 合并代价 O(n)/ \ / \n/4 n/4 n/4 n/4 → 合并代价 O(n)... → 共 log n 层总代价 O(n) × log n O(n log n)。5. 三大关键优化优化一小数组切换插入排序当子数组长度小于某个阈值通常 7~16时直接使用插入排序。因为小数组上插入排序的常数因子远小于归并排序的递归开销。这也是 Timsort 的做法。def merge_sort_optimized(arr, threshold7): if len(arr) threshold: return insertion_sort(arr) mid len(arr) // 2 left merge_sort_optimized(arr[:mid], threshold) right merge_sort_optimized(arr[mid:], threshold) return merge(left, right)优化二合并前判断是否已有序如果arr[mid] arr[mid1]说明左半部分的最大值 ≤ 右半部分的最小值整个数组已经有序无需合并。private static void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); // 优化已经有序就不合并 if (arr[mid] arr[mid 1]) return; merge(arr, left, mid, right); }优化三原地归并In-place Merge标准归并需要 O(n) 额外空间。原地归并可以将空间降到 O(1)但实现复杂且常数因子大实际工程中很少使用。更实用的是迭代版归并自底向上避免递归栈开销def merge_sort_iterative(arr): n len(arr) size 1 while size n: for left in range(0, n, 2 * size): mid min(left size - 1, n - 1) right min(left 2 * size - 1, n - 1) if mid right: merged merge(arr[left:mid1], arr[mid1:right1]) arr[left:right1] merged size * 2 return arr6. 归并排序 vs 快速排序深度对比对比维度归并排序快速排序平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n log n)O(n²)如已有序且选首元素为 pivot空间复杂度O(n)O(log n)递归栈稳定性稳定不稳定数据敏感性不敏感始终 O(n log n)对数据分布敏感实际速度略慢需额外空间拷贝通常更快原地交换适用场景大数据、外排序、要求稳定内存排序、追求速度关键结论归并排序的最坏情况有保证适合对性能稳定性要求高的场景。归并排序是外排序数据太大无法全部装入内存的首选因为可以分块读取、归并写入。Java 的Arrays.sort()对对象数组使用 Timsort归并插入的混合版对基本类型使用双轴快排。7. 适用场景大数据排序数据量超过内存容量时用外归并排序。要求稳定排序如按多个字段排序时保持前一个字段的相对顺序。链表排序归并排序在链表上表现优异因为不需要随机访问且合并只需修改指针。需要最坏情况保证如实时系统不能接受 O(n²) 的退化。作为高级算法的基础如 Timsort、外部排序、MapReduce 中的排序阶段 二、选择排序、归并排序算法讲解
本文是《排序算法系列》第二篇。上一篇我们讲解了冒泡排序和插入排序这一篇我们聚焦选择排序和归并排序。前者以“交换次数少”著称后者则是分治思想的经典代表也是大数据排序的首选之一。选择排序Selection Sort1. 核心思想生活直觉想象你面前有一排打乱的扑克牌你要把它们从小到大排好。你的做法是先扫一遍所有牌找出最小的那张把它放到第一位然后从剩下的牌里再找出最小的放到第二位以此类推。选择排序正是如此每一轮从未排序区间中选出最小或最大的元素放到已排序区间的末尾。它不像冒泡那样频繁交换而是“先看准再动手”——一轮只交换一次。2. 详细执行步骤手把手模拟假设我们要对数组升序排列[5, 1, 4, 2, 8]初始状态整个数组都是未排序区。第 1 轮i 0目标把最小值放到下标 0假设最小值下标min_idx 0值为 5遍历未排序区遇到1下标 11 5更新min_idx 1遇到44 1否不动遇到22 1否不动遇到88 1否不动遍历结束最小值是1与下标 0 的5交换 →[1, 5, 4, 2, 8]已排序区[1]第 2 轮i 1目标把次小值放到下标 1假设min_idx 1值为 5遍历未排序区下标 2 到 4遇到44 5更新min_idx 2遇到22 4更新min_idx 3遇到88 2否不动最小值是2与下标 1 的5交换 →[1, 2, 4, 5, 8]已排序区[1, 2]第 3 轮i 2假设min_idx 2值为 4遍历未排序区下标 3 到 4遇到55 4否不动遇到88 4否不动最小值就是4无需交换 →[1, 2, 4, 5, 8]第 4 轮i 3假设min_idx 3值为 5遍历未排序区下标 4遇到88 5否不动最小值就是5无需交换排序完成3. 标准代码实现Pythondef selection_sort(arr): n len(arr) # 外层循环确定第 i 个位置应该放哪个元素 for i in range(n - 1): 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 arrJavapublic static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } int temp arr[i]; arr[i] arr[minIdx]; arr[minIdx] temp; } }Cvoid selectionSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } swap(arr[i], arr[minIdx]); } }4. 时间复杂度与空间复杂度硬核分析维度详情最坏时间复杂度O(n²) —— 无论数据如何比较次数固定为 n(n-1)/2最好时间复杂度O(n²) —— 即使数组已经有序仍需完整遍历找最小值平均时间复杂度O(n²)空间复杂度O(1) —— 原地排序只用几个临时变量稳定性不稳定—— 例如[5, 5, 1]第一轮将第一个 5 与 1 交换两个 5 的相对顺序被破坏关键特点选择排序的比较次数和交换次数是分离的。比较次数始终是 O(n²)但交换次数最多只有 n-1 次。这是它相对于冒泡排序的最大优势——当“交换”操作代价很高时比如元素是大型结构体选择排序反而更划算。5. 三大关键优化优化一二元选择排序同时找最大和最小每一轮同时找出最小值和最大值分别放到两端。这样外层循环次数减半比较次数虽仍是 O(n²)但常数因子减小。def selection_sort_bidirectional(arr): n len(arr) left, right 0, n - 1 while left right: min_idx, max_idx left, left for i in range(left, right 1): if arr[i] arr[min_idx]: min_idx i if arr[i] arr[max_idx]: max_idx i # 先交换最小值到左端 arr[left], arr[min_idx] arr[min_idx], arr[left] # 注意如果最大值原本在 left 位置交换后它跑到了 min_idx if max_idx left: max_idx min_idx arr[right], arr[max_idx] arr[max_idx], arr[right] left 1 right - 1 return arr优化二记录索引而非立即交换标准实现已经是这样做的——先遍历找最小值下标最后才交换一次。不要写成“发现更小就立即交换”那会退化成冒泡排序。优化三堆排序选择排序的终极进化选择排序的瓶颈在于“找最小值”需要 O(n) 遍历。如果用堆来维护未排序区找最小值只需 O(log n)整体复杂度降到 O(n log n)——这就是堆排序。可以说堆排序是选择排序思想的“质变版”。6. 与其他排序算法的对比算法平均时间复杂度交换次数是否稳定特点选择排序O(n²)最多 n-1 次不稳定交换少比较多冒泡排序O(n²)最多 n(n-1)/2 次稳定交换频繁插入排序O(n²)最多 n(n-1)/2 次移动稳定对部分有序极快堆排序O(n log n)O(n log n)不稳定选择排序的升级版一句话总结选择排序是“交换次数最少”的 O(n²) 算法适合交换代价高、数据量小的场景。7. 适用场景数据规模小n 50且交换操作代价高如元素为大型对象。对稳定性没有要求的场景。教学演示帮助理解“选择”与“交换”的分离。作为堆排序的入门铺垫。归并排序Merge Sort1. 核心思想生活直觉想象你手上有两叠已经按从小到大排好的扑克牌你要把它们合并成一叠有序的牌。你只需要比较两叠牌最上面的那张谁小就先拿谁重复这个过程即可。归并排序的核心就是分治Divide and Conquer分把数组从中间切成两半递归地对左右两半排序。治把两个已经有序的子数组合并成一个有序数组。就像把一个大问题拆成两个小问题解决后再把结果“拼”起来。2. 详细执行步骤手把手模拟假设我们要对数组升序排列[5, 1, 4, 2, 8]第一步分递归拆分[5, 1, 4, 2, 8]↓ 从中间切[5, 1] [4, 2, 8]↓ ↓[5] [1] [4] [2, 8]↓[2] [8]第二步治合并合并[5]和[1]→[1, 5]合并[2]和[8]→[2, 8]合并[4]和[2, 8]→[2, 4, 8]合并[1, 5]和[2, 4, 8]→[1, 2, 4, 5, 8]重点看最后一次合并[1, 5]和[2, 4, 8]步骤左指针右指针比较结果数组1121 2取 1[1]2525 2取 2[1, 2]3545 4取 4[1, 2, 4]4585 8取 5[1, 2, 4, 5]5空8左边空取 8[1, 2, 4, 5, 8]排序完成3. 标准代码实现Pythondef merge_sort(arr): 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 resultJavapublic static void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); // 递归左半 mergeSort(arr, mid 1, right); // 递归右半 merge(arr, left, mid, right); // 合并 } private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; System.arraycopy(temp, 0, arr, left, temp.length); }Cvoid merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } } void mergeSort(vectorint arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }4. 时间复杂度与空间复杂度硬核分析维度详情最坏时间复杂度O(n log n) —— 无论数据如何拆分深度为 log n每层合并 O(n)最好时间复杂度O(n log n) —— 即使已经有序仍需完整拆分和合并平均时间复杂度O(n log n)空间复杂度O(n)—— 合并时需要额外数组这是归并排序的最大缺点稳定性稳定—— 合并时用保证相等元素左边优先递归树分析n → 合并代价 O(n)/ \n/2 n/2 → 合并代价 O(n)/ \ / \n/4 n/4 n/4 n/4 → 合并代价 O(n)... → 共 log n 层总代价 O(n) × log n O(n log n)。5. 三大关键优化优化一小数组切换插入排序当子数组长度小于某个阈值通常 7~16时直接使用插入排序。因为小数组上插入排序的常数因子远小于归并排序的递归开销。这也是 Timsort 的做法。def merge_sort_optimized(arr, threshold7): if len(arr) threshold: return insertion_sort(arr) mid len(arr) // 2 left merge_sort_optimized(arr[:mid], threshold) right merge_sort_optimized(arr[mid:], threshold) return merge(left, right)优化二合并前判断是否已有序如果arr[mid] arr[mid1]说明左半部分的最大值 ≤ 右半部分的最小值整个数组已经有序无需合并。private static void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); // 优化已经有序就不合并 if (arr[mid] arr[mid 1]) return; merge(arr, left, mid, right); }优化三原地归并In-place Merge标准归并需要 O(n) 额外空间。原地归并可以将空间降到 O(1)但实现复杂且常数因子大实际工程中很少使用。更实用的是迭代版归并自底向上避免递归栈开销def merge_sort_iterative(arr): n len(arr) size 1 while size n: for left in range(0, n, 2 * size): mid min(left size - 1, n - 1) right min(left 2 * size - 1, n - 1) if mid right: merged merge(arr[left:mid1], arr[mid1:right1]) arr[left:right1] merged size * 2 return arr6. 归并排序 vs 快速排序深度对比对比维度归并排序快速排序平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n log n)O(n²)如已有序且选首元素为 pivot空间复杂度O(n)O(log n)递归栈稳定性稳定不稳定数据敏感性不敏感始终 O(n log n)对数据分布敏感实际速度略慢需额外空间拷贝通常更快原地交换适用场景大数据、外排序、要求稳定内存排序、追求速度关键结论归并排序的最坏情况有保证适合对性能稳定性要求高的场景。归并排序是外排序数据太大无法全部装入内存的首选因为可以分块读取、归并写入。Java 的Arrays.sort()对对象数组使用 Timsort归并插入的混合版对基本类型使用双轴快排。7. 适用场景大数据排序数据量超过内存容量时用外归并排序。要求稳定排序如按多个字段排序时保持前一个字段的相对顺序。链表排序归并排序在链表上表现优异因为不需要随机访问且合并只需修改指针。需要最坏情况保证如实时系统不能接受 O(n²) 的退化。作为高级算法的基础如 Timsort、外部排序、MapReduce 中的排序阶段