C++ 笔记 2026-06-03

排序算法 pt.1

选择排序

例：数组list[8, 7, 6, 5, 4, 3, 2, 1], length=8

• 第一次 1, 7, 6, 5, 4, 3, 2, 8 (list[0]到list[7]最小为list[7](1)，与第1位的8交换)
• 第二次 1, 2, 6, 5, 4, 3, 7, 8 (list[1]到list[7]最小为list[6](2)，与第2位的7交换)
• 第三次 1, 2, 3, 5, 4, 6, 7, 8 (list[2]…最小为list[5](3)，与第3位的6交换)
  …

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  #include <iostream> using namespace std; const long long N = 1e5+9; int list[N]; void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> list[i]; } for (int i = 0; i < n-1; i++) { int min_index = i; for(int j = i + 1; j < n-1-i; j++) { if (list[min_index]>list[j]) min_index = j; } swap(&list[min_index], &list[i]) } }

冒泡排序

以从小到大为例，比较相邻两个数，如果前面的比后面的大，那么就交换这两个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
using namespace std;
const long long N = 1e5+9;
int list[N];
void swap(int* a, int* b) {
	int t = *a;
	*a = *b;
	*b = t;
}
int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> list[i];
	}
	list[n]=1e5; // max: 1e4
	for (int i = 0; i < n; i++) {
		bool ordered = false;
		for (int j = 0; j < n; j++) {
			if(list[j]>list[j+1]) {
				swap(&list[j], list[j+1]);
				ordered = true;
			}
		}
		if (!ordered) break;
	}
}