第十二章：排序算法——让数据井然有序¶
你好！欢迎来到第十二章！在日常生活中，我们经常需要把东西排好序，比如按身高排队、按分数排名、按时间顺序排列照片。在计算机科学中，排序是最基础也最重要的算法之一。虽然C++的STL提供了强大的 sort 函数，但学习排序算法能帮助我们理解计算机如何工作，锻炼逻辑思维。这一章我们就来学习几种经典的排序算法，并亲手实现它们！
12.1 什么是排序算法？¶
排序就是将一组数据按照某种规则重新排列，比如从小到大（升序）或从大到小（降序）。
想象你有一堆乱序的扑克牌，你要把它们按数字从小到大整理好。你会怎么做？不同的方法对应不同的排序算法。
本章我们将学习：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序（进阶）
- 归并排序（进阶）
12.2 冒泡排序¶
12.2.1 算法思想¶
冒泡排序就像水中的气泡，轻的气泡会慢慢浮到上面。每次比较相邻的两个元素，如果顺序不对（比如前大后小），就交换它们。这样每一轮都会把最大的数“冒泡”到最后。
过程演示（升序）：
初始数组：[5, 3, 8, 1, 2]
第一轮：
- 比较5和3，5>3，交换 → [3, 5, 8, 1, 2]
- 比较5和8，5<8，不交换 → [3, 5, 8, 1, 2]
- 比较8和1，8>1，交换 → [3, 5, 1, 8, 2]
- 比较8和2，8>2，交换 → [3, 5, 1, 2, 8]（最大数8已就位）
第二轮：
- 比较3和5，3<5，不交换 → [3, 5, 1, 2, 8]
- 比较5和1，5>1，交换 → [3, 1, 5, 2, 8]
- 比较5和2，5>2，交换 → [3, 1, 2, 5, 8]（次大数5就位）
第三轮：
- 比较3和1，3>1，交换 → [1, 3, 2, 5, 8]
- 比较3和2，3>2，交换 → [1, 2, 3, 5, 8]（第三大3就位）
第四轮：
- 比较1和2，1<2，不交换 → 已完成
12.2.2 代码实现¶
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // 需要 n-1 轮
for (int j = 0; j < n - 1 - i; j++) { // 每轮比较次数减少
if (arr[j] > arr[j + 1]) { // 如果前大后小，交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 3, 8, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "排序后：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
12.2.3 优化¶
如果某一轮没有发生任何交换，说明数组已经有序，可以提前结束。
void bubbleSortOptimized(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 标记是否交换
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]); // 可以用swap函数
swapped = true;
}
}
if (!swapped) break; // 没有交换，退出
}
}
12.2.4 阶段性练习¶
- 练习1：用冒泡排序对数组 [9, 2, 5, 1, 7] 进行升序排序，写出每轮结果。
- 练习2：实现降序冒泡排序（从大到小）。
- 练习3：统计冒泡排序中交换的次数。
12.3 选择排序¶
12.3.1 算法思想¶
选择排序的思路很简单：每一轮从未排序的部分中找出最小的元素，放到已排序部分的末尾。
过程演示（升序）：
初始：[5, 3, 8, 1, 2]
- 第一轮：找到最小元素1，与第一个元素5交换 → [1, 3, 8, 5, 2]
- 第二轮：从剩余[3,8,5,2]中找到最小2，与第二个元素3交换 → [1, 2, 8, 5, 3]
- 第三轮：从剩余[8,5,3]中找到最小3，与第三个元素8交换 → [1, 2, 3, 5, 8]
- 第四轮：从剩余[5,8]中找到最小5，与第四个元素5（自身）不交换 → 完成
12.3.2 代码实现¶
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 假设当前是最小
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小下标
}
}
if (minIndex != i) { // 交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
12.3.3 阶段性练习¶
- 练习1：用选择排序对数组 [8, 3, 6, 1, 4] 排序，写出每轮结果。
- 练习2：实现降序选择排序。
- 练习3：选择排序的交换次数最多是多少？
12.4 插入排序¶
12.4.1 算法思想¶
插入排序就像整理扑克牌：每次将一张牌插入到已经有序的手牌中的正确位置。
过程演示（升序）：
初始：[5, 3, 8, 1, 2]
- 第一张牌5，有序部分：[5]
- 取3，插入到5前面 → [3, 5, 8, 1, 2]
- 取8，比5大，位置不变 → [3, 5, 8, 1, 2]
- 取1，依次比较8、5、3，插入最前 → [1, 3, 5, 8, 2]
- 取2，依次比较8、5、3，插入3和1之间 → [1, 2, 3, 5, 8]
12.4.2 代码实现¶
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前要插入的元素
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 向后移动
j--;
}
arr[j + 1] = key; // 插入正确位置
}
}
12.4.3 阶段性练习¶
- 练习1：用插入排序对 [7, 2, 5, 1, 9] 排序，写出每一步后数组的变化。
- 练习2：实现降序插入排序。
- 练习3：插入排序在什么情况下最快？什么情况下最慢？
12.5 快速排序（进阶）¶
12.5.1 算法思想¶
快速排序采用分治策略：选择一个基准值（pivot），将数组分成两部分，左边都比基准小，右边都比基准大，然后递归地对左右两部分排序。
过程演示（以第一个元素为基准）：
数组：[5, 3, 8, 1, 2]
- 基准5，从右找小于5的2，从左找大于5的8，交换2和8 → [5, 3, 2, 1, 8]
- 继续，从右找小于5的1，从左找大于5的没有，交换1和基准位置？实际上标准做法是用两个指针，最终将基准放到正确位置。
最终得到 [2, 3, 1, 5, 8]，左边都小于5，右边大于5。
- 递归排序左边 [2,3,1] 和右边 [8]。
12.5.2 代码实现¶
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 选第一个为基准
int i = low, j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) j--; // 从右找小于pivot的
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] <= pivot) i++; // 从左找大于pivot的
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot; // 基准归位
return i; // 返回基准位置
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
调用时：quickSort(arr, 0, n-1);
12.5.3 阶段性练习¶
- 练习1：模拟快速排序对 [4, 7, 2, 1, 5, 3] 的过程。
- 练习2：尝试以中间元素为基准实现快速排序。
12.6 排序算法的比较¶
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
稳定性：如果两个相等的元素在排序前后的相对位置不变，则排序算法是稳定的。
12.7 编程实例讲解¶
实例1：成绩排序¶
题目：输入n个学生的姓名和成绩，按成绩从高到低排序，如果成绩相同则按姓名字典序排序。
#include <iostream>
#include <string>
#include <algorithm> // 用sort，但我们可以手写排序
using namespace std;
struct Student {
string name;
int score;
};
// 冒泡排序（按成绩降序，成绩相同按姓名升序）
void sortStudents(Student stu[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (stu[j].score < stu[j + 1].score ||
(stu[j].score == stu[j + 1].score && stu[j].name > stu[j + 1].name)) {
swap(stu[j], stu[j + 1]);
}
}
}
}
int main() {
int n;
cout << "请输入学生人数：";
cin >> n;
Student stu[100];
for (int i = 0; i < n; i++) {
cin >> stu[i].name >> stu[i].score;
}
sortStudents(stu, n);
cout << "\n排序结果：" << endl;
for (int i = 0; i < n; i++) {
cout << stu[i].name << " " << stu[i].score << endl;
}
return 0;
}
实例2：排序算法效率对比¶
用随机数生成大量数据，测试不同排序算法的时间。
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// 冒泡排序、选择排序、插入排序、快速排序函数声明...
int main() {
const int N = 10000;
int arr1[N], arr2[N], arr3[N], arr4[N];
srand(time(0));
for (int i = 0; i < N; i++) {
int val = rand() % 10000;
arr1[i] = arr2[i] = arr3[i] = arr4[i] = val;
}
clock_t start, end;
start = clock();
bubbleSort(arr1, N);
end = clock();
cout << "冒泡排序时间：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;
// 测试其他排序...
return 0;
}
12.8 第12章编程作业¶
作业1：三种简单排序的对比¶
编写程序，生成1000个随机整数，分别用冒泡、选择、插入排序进行排序，并输出每种排序的交换次数和比较次数（在代码中加入计数器）。
作业2：排序字符串数组¶
输入若干单词（字符串），用插入排序按字典序排序输出。
作业3：快速排序的实现¶
实现快速排序，并测试其效率。
作业4：排序稳定性验证¶
创建一个包含姓名和分数的结构体数组，其中有两个同分不同名的学生。分别用稳定和不稳定的排序算法排序，观察他们的相对顺序是否改变。
作业5：自定义排序规则¶
编写一个程序，按以下规则对整数排序：奇数在前，偶数在后；奇数按升序，偶数按降序。例如 [3,2,5,1,8,4] 排序后应为 [1,3,5,8,4,2]。
恭喜你完成了第十二章的学习！现在你已经掌握了多种排序算法，能够处理各种排序问题了。加油！🚀