排序算法
概念讲解
常见排序算法
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
基础排序
冒泡排序
123456789void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}
}选择排序
123456789void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) minIdx = j;
}
swap(a[i], a[minIdx]);
}
}插入排序
12345678910void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}STL sort
基本用法
1234567#include <algorithm>
int a[] = {3, 1, 4, 1, 5};
sort(a, a + 5); // 升序
vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());自定义比较
12345678// 降序
sort(a, a + n, greater<int>());
// 自定义比较函数
bool cmp(int a, int b) {
return a > b;
}
sort(a, a + n, cmp);考点分析
初赛考查方式
- 选择题： 排序算法特性
- 程序阅读： 手动模拟排序
- 编程题： 排序应用
常见考点
- 排序算法时间复杂度
- 稳定性判断
- 手动模拟排序过程
例题精讲
例题 1：冒泡排序
题目： 对 [3, 1, 4, 1, 5] 进行冒泡排序。
解答：
第1轮: [1, 3, 1, 4, 5]
第2轮: [1, 1, 3, 4, 5]
第3轮: [1, 1, 3, 4, 5]例题 2：STL sort
题目： 对 vector 降序排序。
解答：
1sort(v.begin(), v.end(), greater<int>());练习题
- 哪些排序算法是稳定的？
查看答案
稳定排序：冒泡排序、插入排序、归并排序
不稳定排序：选择排序、快速排序
稳定排序会保持相等元素的相对顺序不变。
- 快速排序的平均时间复杂度是多少？
查看答案
平均时间复杂度：
最坏时间复杂度：（当数组已经有序时）
空间复杂度：（递归栈）
- 如何对结构体数组排序？
查看答案
使用自定义比较函数：
1234567891011struct Student {
string name;
int score;
};
bool cmp(Student a, Student b) {
return a.score > b.score; // 按分数降序
}
Student s[] = {{"Alice", 90}, {"Bob", 85}};
sort(s, s + 2, cmp);易错点
⚠️ 注意：
- 快速排序最坏 O(n²)
- 稳定排序保持相等元素的相对顺序
- sort 默认升序
- 自定义比较函数要严格弱序