以下是为您编写的三大基础排序算法（冒泡排序、选择排序、插入排序）讲义。本讲义采用系统化的教学结构，包含算法的核心思想、标准 C++ 实现、多维度复杂度分析、算法稳定性探讨以及针对性的优化方案与改进代码。
基础数据结构与算法讲义：三大基础排序算法
在计算机科学中，冒泡排序 (Bubble Sort)、选择排序 (Selection Sort) 和 插入排序 (Insertion Sort) 被统称为“三大基础排序算法”。它们都是原地排序算法 (In-place Sort)，时间复杂度主要集中在 $O(n^2)$。尽管它们在面对大规模数据时效率较低，但其简单的实现逻辑、极低的额外空间占用，使其在小规模数据处理或作为高级排序算法（如快速排序、归并排序）的底层子程序时，依然发挥着重要作用。
目录
1. 冒泡排序 (Bubble Sort)
1.1 核心思想
冒泡排序通过相邻元素的比较与交换，使较大（或较小）的元素逐渐“浮”到数组的一端。 * 每一轮遍历中，从头到尾依次比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们。 * 经过第一轮遍历，最大值会被交换到数组的最右端。 * 随后，对剩下的 $n-1$ 个元素重复上述过程。共需进行 $n-1$ 轮。
1.2 标准 C++ 代码实现
#include <vector>
#include <algorithm>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
// 每一轮遍历，最大的元素会沉到最右侧，因此内层循环边界递减
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
1.3 复杂度与稳定性分析
- 时间复杂度：
- 最好情况： $O(n^2)$。即使数组已经完全有序，标准实现仍会执行双重循环进行比较。
- 最坏情况： $O(n^2)$。当数组完全逆序时，需要执行完整的 $\frac{n(n-1)}{2}$ 次比较与等数量级的交换。
- 平均情况： $O(n^2)$。
- 空间复杂度： $O(1)$。仅需常数级别的辅助变量用于交换。
- 稳定性： 稳定。由于只有在
arr[j] > arr[j + 1]（严格大于）时才发生交换，若两元素相等则不会交换，因此不会改变相同元素的相对顺序。
1.4 改进与优化方式
优化点 A：设置交换标志位 (Flag)
若某次外层循环中，内层循环未发生任何一次数据交换，说明此时数组已经完全有序，可提前终止算法。这能将最好情况下的时间复杂度降为 $O(n)$。
优化点 B：记录最后一次交换的位置 (Boundary)
在每一轮遍历中，最后一次发生交换的位置之后的元素必然已经有序。我们可以记录这个位置，作为下一轮内层循环的终点，从而避免无效的比较。
改进后 C++ 代码：
void optimizedBubbleSort(std::vector<int>& arr) {
int n = arr.size();
int lastSwapIndex = n - 1; // 记录最后一次交换的索引边界
while (lastSwapIndex > 0) {
int k = 0; // 临时变量，记录当前轮次最后一次交换的位置
bool swapped = false;
for (int j = 0; j < lastSwapIndex; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
k = j; // 更新交换位置
swapped = true;
}
}
if (!swapped) break; // 如果一整轮未发生交换，直接退出
lastSwapIndex = k; // 下一轮的比较终点限制在最后一次交换的位置
}
}
2. 选择排序 (Selection Sort)
2.1 核心思想
选择排序的思想是选择极值并放置到已排序区间的末尾。 * 将整个数组划分为“已排序区间”和“未排序区间”。初始时，已排序区间为空。 * 每次从未排序区间中找到最小（或最大）的元素，将其与未排序区间的首个元素交换。 * 交换后，该元素归入已排序区间。重复此过程，直到未排序区间只剩一个元素。
2.2 标准 C++ 代码实现
#include <vector>
#include <algorithm>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIdx = i; // 假设未排序区间的首个元素为最小值
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIdx]) {
minIdx = j; // 更新最小值的索引
}
}
if (minIdx != i) {
std::swap(arr[i], arr[minIdx]); // 将最小值交换到已排序区间的末尾
}
}
}
2.3 复杂度与稳定性分析
- 时间复杂度：
- 无论数组初始状态如何，选择排序的比较次数始终为 $\frac{n(n-1)}{2}$，因此最好、最坏、平均时间复杂度均为 $O(n^2)$。其优势在于，数据交换的次数最多只有 $n-1$ 次。
- 空间复杂度： $O(1)$。
- 稳定性： 不稳定。
- 反例： 考虑数组 $[5, 8, 5, 2, 9]$。第一轮搜索中，最小元素是 $2$，它会与第一个 $5$ 交换。交换后，第一个 $5$ 到了 $2$ 的位置，位于第二个 $5$ 的后面，原有的相对顺序被破坏。
2.4 改进与优化方式
优化点：二元选择排序 (Double-ended Selection Sort)
普通的算法每次只寻找最小值。我们可以通过双指针，在一轮遍历中同时找出最大值和最小值。将最小值与未排序区间头部交换，最大值与未排序区间尾部交换。这样可以将外部循环次数减少一半。
注意：在交换最大值时，需注意边界情况。如果最大值刚好位于未排序区间的头部，那么在交换最小值时，最大值的位置会被移走，代码中必须对此进行修正。
改进后 C++ 代码：
void doubleSelectionSort(std::vector<int>& arr) {
int left = 0;
int right = arr.size() - 1;
while (left < right) {
int minIdx = left;
int maxIdx = left;
for (int j = left + 1; j <= right; ++j) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
if (arr[j] > arr[maxIdx]) {
maxIdx = j;
}
}
// 1. 将最小值交换到最左边
std::swap(arr[left], arr[minIdx]);
// 特殊情况：如果当前最大值恰好在最左侧(left)，它已经被换到了原 minIdx 的位置
if (maxIdx == left) {
maxIdx = minIdx; // 更新最大值的索引位置
}
// 2. 将最大值交换到最右边
std::swap(arr[right], arr[maxIdx]);
left++;
right--;
}
}
3. 插入排序 (Insertion Sort)
3.1 核心思想
插入排序类似于整理扑克牌。 * 将数组分为“已排序”和“未排序”两部分。初始时，将第一个元素视为已排序区间。 * 每次从未排序区间取出一个元素 $key$，在已排序区间中从右向左依次扫描，找到其合适的插入位置。 * 在扫描过程中，将所有大于 $key$ 的已排序元素依次向右移动一位，留出空位给 $key$ 插入。
3.2 标准 C++ 代码实现
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i]; // 当前待插入的目标值
int j = i - 1;
// 将大于 key 的元素向右移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入到正确位置
}
}
3.3 复杂度与稳定性分析
- 时间复杂度：
- 最好情况： $O(n)$。当输入数组已经完全有序时，内层
while循环每次只比较一次即退出，整体只需比较 $n-1$ 次。 - 最坏情况： $O(n^2)$。数组完全逆序，每次都需要移动前面所有的元素。
- 平均情况： $O(n^2)$。对于局部有序或元素规模较小的数据，插入排序的性能表现通常在 $O(n^2)$ 级算法中最为优秀。
- 空间复杂度： $O(1)$。
- 稳定性： 稳定。因为只有当已排序元素
arr[j] > key（严格大于）时，才进行移动。相等的元素不会发生相对位移。
3.4 改进与优化方式
优化点 A：折半插入排序 (Binary Insertion Sort)
在已排序区间中寻找插入位置时，默认使用的是顺序查找。由于已排序区间是有序的，我们可以使用二分查找 (Binary Search) 来确定插入位置。虽然这无法减少元素移动的物理开销（仍为 $O(n^2)$ 级别），但能将比较次数优化至 $O(n \log n)$。
优化点 B：希尔排序 (Shell Sort)
希尔排序是插入排序的一种高速衍生版本。它通过设置一个递减的步长（Gap）序列，对相隔固定步长的子数组执行插入排序，逐步使数组整体“几乎有序”，最后执行一次步长为 $1$ 的标准插入排序。这使最坏时间复杂度成功突破了 $O(n^2)$。
改进代码一：折半插入排序
void binaryInsertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int left = 0;
int right = i - 1;
// 1. 利用二分查找确定插入位置
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1; // 保持稳定性：遇到相等的元素，新元素仍插在其右侧
}
}
// 2. 将 [left, i-1] 范围内的元素统一向右移动一位
for (int j = i - 1; j >= left; --j) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
改进代码二：希尔排序 (Shell Sort)
void shellSort(std::vector<int>& arr) {
int n = arr.size();
// 采用 Shell 原始增量序列: n/2, n/4, ..., 1
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; ++i) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
4. 三大排序综合对比
| 算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 核心优化手段 |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 设置交换 Flag、记录边界 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | 二元选择（双端寻值） |
| 插入排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 折半查找位置、希尔排序 |
总结建议
- 优先考虑插入排序： 在三大基础 $O(n^2)$ 排序中，插入排序在实际工业运行中的耗时最短。这是因为其内层循环的指令非常精简，且在“几乎有序”的实际数据中表现极其优异（如
std::sort在递归深度较浅且子区间小于一定阈值时，通常会切换为插入排序）。 - 选择排序的特定场景： 选择排序虽然不稳定且平均耗时较长，但其数据交换次数最少（最多 $n-1$ 次）。如果在某些场景中，数据的写入/交换代价极大（例如 Flash 闪存介质），选择排序比冒泡、插入排序更适用。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
