课程进度 91% · 第10/10章第10/10章 · 标签 1/7
— 1 —
排序算法全解析
排序算法是算法面试的基础，也是理解算法复杂度与设计思想的良好入口。本专题详细介绍常见排序算法的原理、实现与应用。
排序算法对比
| 算法 | 平均 | 最好 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | 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^1.3) | O(n) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | 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(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n) | O(n²) | O(n+k) | 稳定 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 |
📖实际应用中，小规模数据用插入排序，中等规模用快速排序，大规模且要求稳定用归并排序，特定范围整数用计数排序。
— 2 —
冒泡排序
原理：每次遍历将未排序区间中最大的元素「冒泡」到末尾。
cpp
1
void bubbleSort(vector<int>& arr) {
2
int n = arr.size();
3
for (int i = 0; i < n - 1; ++i) {
4
bool swapped = false;
5
for (int j = 0; j < n - 1 - i; ++j) {
6
if (arr[j] > arr[j + 1]) {
7
swap(arr[j], arr[j + 1]);
8
swapped = true;
9
}
10
}
11
if (!swapped) break;
12
}
13
}
快速排序
原理：选定基准，将数组分为小于和大于基准两部分，递归排序。
cpp
1
void quickSort(vector<int>& arr, int l, int r) {
2
if (l >= r) return;
3
int pivot = arr[r];
4
int i = l - 1;
5
for (int j = l; j < r; ++j) {
6
if (arr[j] < pivot) swap(arr[++i], arr[j]);
7
}
8
swap(arr[i + 1], arr[r]);
9
int mid = i + 1;
10
quickSort(arr, l, mid - 1);
11
quickSort(arr, mid + 1, r);
12
}
排序冒泡快排归并堆排插入排序