排序算法
🔄 排序算法可视化
Section titled “🔄 排序算法可视化”排序是最基础也最重要的算法之一。面试必考，工作常用。
🔄排序算法可视化
冒泡排序相邻元素两两比较，大的往后冒泡
最优 O(n)平均 O(n²)最差 O(n²)空间 O(1)
数组大小:8
速度:中
14
48
8
28
78
31
38
17
步骤 1 / 0
比较中
交换中
已排序
Pivot
📊 算法对比速查表
Section titled “📊 算法对比速查表”| 算法 | 最优 | 平均 | 最差 | 空间 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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 log n) | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 | 内存敏感 |
🎯 核心思想
Section titled “🎯 核心思想”冒泡排序 - 相邻交换
Section titled “冒泡排序 - 相邻交换”function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 相邻交换 } } }}记忆点: 大泡泡往上冒，每轮确定一个最大值
选择排序 - 选最小
Section titled “选择排序 - 选最小”function selectionSort(arr) { for (let i = 0; i < arr.length; i++) { let minIdx = i; for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; // 放到前面 }}记忆点: 每轮选出最小的，放到已排序部分末尾
插入排序 - 扑克牌
Section titled “插入排序 - 扑克牌”function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { const key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 向右腾位置 j--; } arr[j + 1] = key; // 插入 }}记忆点: 像整理扑克牌，把新牌插入正确位置
快速排序 - 分治
Section titled “快速排序 - 分治”function quickSort(arr, low = 0, high = arr.length - 1) { if (low < high) { const pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); // 左半部分 quickSort(arr, pivot + 1, high); // 右半部分 }}
function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1;}记忆点: 选基准、分两边、递归排
💡 面试高频问题
Section titled “💡 面试高频问题”1. 什么是稳定排序？
Section titled “1. 什么是稳定排序？”相等元素的相对顺序在排序后保持不变。
稳定: 冒泡、插入、归并
不稳定: 选择、快排、堆排序
2. 为什么快排平均最快？
Section titled “2. 为什么快排平均最快？”- 原地排序，缓存友好
- 分治减少比较次数
- 实际数据随机性好
3. 什么时候用插入排序？
Section titled “3. 什么时候用插入排序？”- 数据量小 (n < 50)
- 数据近乎有序
- 作为快排的优化 (小区间切换)
4. 归并 vs 快排？
Section titled “4. 归并 vs 快排？”| 维度 | 归并 | 快排 |
|---|---|---|
| 最差复杂度 | O(n log n) ✅ | O(n²) ❌ |
| 空间复杂度 | O(n) ❌ | O(log n) ✅ |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 |
| 缓存友好 | ❌ | ✅ |