U170921.U4-04 排序综合📚

1. 冒泡排序

核心思想：重复地走访要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作重复进行，直到没有相邻元素需要交换。

#include <iostream>
using namespace std;
int n;
int a[1010];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	// n-1 轮冒泡
	for (int i = 1; i <= n - 1; i++) {
		// 第i轮冒泡，需要相邻两两比较 n-i 次
		for (int j = 1; j <= n - i; j++) {
			if (a[j] > a[j + 1]) {          // > 交换 → 从小到大
				swap(a[j], a[j + 1]);       // 改成 < 交换 → 从大到小
			}
		}
	}
	// 输出排序后的数组
	for (int i = 1; i <= n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

2. 选择排序

核心思想：第一次从所有数字中找到最小（大）值和第一个位置交换，第二次从剩下数字中找到最小（大）值和第二个位置交换，以此类推，直到所有数字都排序完。

#include <iostream>
using namespace std;
int a[1010];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	// 选择排序
	for (int i = 1; i <= n - 1; i++) {  // n-1 趟
		// 一趟选择：找第i小的位置k，然后交换到第i个位置
		int k = i;
		for (int j = k + 1; j <= n; j++) {
			if (a[j] < a[k]) {
				k = j;
			}
		}
		swap(a[i], a[k]);
	}
	// 输出排序后的数组
	for (int j = 1; j <= n; j++) {
		cout << a[j] << " ";
	}
	cout << endl;
	return 0;
}

3. 插入排序

核心思想：往 n 个元素的序列中插入第 n+1 个元素，插入后得到一个新的、元素个数增 1 的序列，并使得该序列仍然有序。

for (int i = 2; i <= n; i++) {
	int x = a[i];       // 待插入元素
	int j = i - 1;      // 已有序的元素范围
	while (j >= 1 && a[j] > x) {
		a[j + 1] = a[j];
		j--;
	}
	a[j + 1] = x;
}

4. 计数排序

计数排序也叫桶排序，下面就用"桶"来说。

适用场景：待排序的值在一个明显有限的范围内（整型）时适用。

做法：设计有限个有序桶，将待排序的值装入对应的桶中，桶号是待排序的值。当桶内元素大于 0 时，顺序输出桶的标号，元素的值是几就输出几次。

#include <iostream>
using namespace std;
int cnt[110];  // 1~100，cnt[x] 表示 x 出现的次数
int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		cnt[x]++;
	}
	// 遍历数字的范围 (1~100)
	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= cnt[i]; j++) {
			cout << i << " ";
		}
	}
	return 0;
}

5. sort 排序

功能：对给定区间所有元素进行排序（默认升序）

头文件：<algorithm>

基础语法

sort(首元素地址, 尾元素的下一个地址, 比较函数);

自定义比较函数 cmp

// 降序排列
bool cmp(int a, int b) {
	return a > b;  // a 大于 b，则 a 排在 b 前面
}
// 升序排列
bool cmp(int a, int b) {
	return a < b;  // a 小于 b，则 a 排在 b 前面
}

使用标准库函数

// 直接传入 greater<int>()
sort(a, a + n, greater<int>());

6. 结构体排序

排序解题四步走

第1步：建结构体类型和结构体数组

1. 审题看排序 + 输出需要几个信息，建立结构体类型。
2. 审题看结构体数组需要多大，建立结构体数组。

第2步：读取信息到结构体数组

信息有的是读取的，有的是需要自己计算/赋值的。

第3步：结构体排序

1. 从题目中 + 输出里面找结构体排序规则，在 cmp 函数里面写嵌套 if 语句。
2. 主函数里面调用 sort 排序。

第4步：输出

7. 稳定性

稳定性专题

定义：两个关键字相同的元素，排序后相对先后顺序保持不变，则称该排序算法是稳定的。

举例：有 (3, A) 和 (3, B)，关键字都是 3。排序前 A 在 B 前面，排序后 A 依然在 B 前面 → 稳定。

易错点：稳定性不是看数值有没有变（数值当然不变），而是看"相等元素的相对顺序"有没有变。

记忆口诀：相等元素不乱跑，就是稳定。

各排序的稳定性

算法	稳定性
冒泡	稳定
选择	不稳定
插入	稳定
计数	标准写法可稳定

助记口诀

稳定：三毛（冒泡）查（插入）询学习轨（归并）迹（基数）→ "差的很稳定"。

不稳定：希（希尔）望快快（快速）选（选择）对（堆）→ 不稳定。

可以只记不稳定的，别的都是稳定的。