课程进度 53% · 第6/10章第6/10章 · 标签 1/3
— 1 —
常用排序算法
掌握经典排序算法的原理与实现：
cpp
1
// 冒泡排序（每轮将最大/最小元素"冒泡"到末尾）
2
void bubbleSort(vector<int>& a) {
3
int n = a.size();
4
for (int i = 0; i < n - 1; ++i) {
5
bool swapped = false;
6
for (int j = 0; j < n - 1 - i; ++j) {
7
if (a[j] > a[j + 1]) {
8
swap(a[j], a[j + 1]);
9
swapped = true;
10
}
11
}
12
if (!swapped) break;
13
}
14
}
15
// 选择排序（每轮选择最小元素放到前面）
16
void selectionSort(vector<int>& a) {
17
int n = a.size();
18
for (int i = 0; i < n - 1; ++i) {
19
int minIdx = i;
20
for (int j = i + 1; j < n; ++j)
21
if (a[j] < a[minIdx]) minIdx = j;
22
swap(a[i], a[minIdx]);
23
}
24
}
25
// 插入排序（将当前元素插入到前面有序区间）
26
void insertionSort(vector<int>& a) {
27
int n = a.size();
28
for (int i = 1; i < n; ++i) {
29
int x = a[i], j = i - 1;
30
while (j >= 0 && a[j] > x) {
31
a[j + 1] = a[j]; --j;
32
}
33
a[j + 1] = x;
34
}
35
}
— 2 —
cpp
1
// 归并排序（分治，递归排序左右两半并合并）
2
void merge(vector<int>& a, int l, int m, int r) {
3
vector<int> tmp(r - l + 1);
4
int i = l, j = m + 1, k = 0;
5
while (i <= m && j <= r)
6
tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
7
while (i <= m) tmp[k++] = a[i++];
8
while (j <= r) tmp[k++] = a[j++];
9
for (int t = 0; t < tmp.size(); ++t) a[l + t] = tmp[t];
10
}
11
void mergeSort(vector<int>& a, int l, int r) {
12
if (l >= r) return;
13
int m = l + (r - l) / 2;
14
mergeSort(a, l, m);
15
mergeSort(a, m + 1, r);
16
merge(a, l, m, r);
17
}
18
// 快速排序（分治，选基准分区递归排序）
19
int partition(vector<int>& a, int l, int r) {
20
int pivot = a[r], i = l - 1;
21
for (int j = l; j < r; ++j) {
22
if (a[j] <= pivot) swap(a[++i], a[j]);
23
}
24
swap(a[i + 1], a[r]);
25
return i + 1;
26
}
27
void quickSort(vector<int>& a, int l, int r) {
28
if (l < r) {
29
int p = partition(a, l, r);
30
quickSort(a, l, p - 1);
31
quickSort(a, p + 1, r);
32
}
33
}
34
// 堆排序（利用大根堆/小根堆，每次取堆顶）
35
void heapify(vector<int>& a, int n, int i) {
36
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
37
if (l < n && a[l] > a[largest]) largest = l;
38
if (r < n && a[r] > a[largest]) largest = r;
39
if (largest != i) { swap(a[i], a[largest]); heapify(a, n, largest); }
40
}
41
void heapSort(vector<int>& a) {
42
int n = a.size();
43
for (int i = n / 2 - 1; i >= 0; --i) heapify(a, n, i);
44
for (int i = n - 1; i > 0; --i) { swap(a[0], a[i]); heapify(a, i, 0); }
45
}
冒泡选择插入归并快排堆排