引言进入《大话数据结构》第9章「排序」。本章从最基础的三种排序算法讲起冒泡排序、简单选择排序、直接插入排序。虽然它们平均时间复杂度都是 O(n²)但思路经典是理解后续高效排序的基础。本文提供三种排序算法的完整 C 实现并附上复杂度分析、稳定性说明、对比表格以及可直接运行的测试代码方便读者对照学习。1. 冒泡排序Bubble Sort核心思想重复比较相邻元素如果顺序错误就交换每一轮把最大的元素“冒泡”到末尾。1.1 代码实现已优化提前结束 记录最后交换位置#include iostream #include vector using namespace std; void BubbleSort(vectorint arr) { int n arr.size(); bool swapped; int lastSwapPos n - 1; // 记录最后一次交换的位置 for (int i 0; i n - 1; i) { swapped false; int currentSwapPos 0; for (int j 0; j lastSwapPos; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; currentSwapPos j; } } if (!swapped) break; // 本轮没有发生交换说明已经有序 lastSwapPos currentSwapPos; } }1.2 复杂度与稳定性指标说明最好时间复杂度O(n)已经有序优化后平均 / 最坏时间复杂度O(n²)空间复杂度O(1)稳定性稳定优化说明基础版冒泡排序每轮都要比较到数组末尾优化版通过lastSwapPos记录最后一次交换的位置下一轮只需比较到该位置即可因为其后元素已经有序。同时用swapped标记本轮是否发生交换若没有交换则提前结束。2. 简单选择排序Selection Sort核心思想每一轮从待排序区间中选出最小的元素放到已排序区间的末尾。2.1 代码实现void SelectionSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { int minIndex i; // 找到从 i 到末尾的最小值下标 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 交换 if (minIndex ! i) { swap(arr[i], arr[minIndex]); } } }2.2 复杂度与稳定性指标说明最好 / 平均 / 最坏时间复杂度都是 O(n²)空间复杂度O(1)稳定性不稳定交换可能跨过相同元素特点交换次数少最多 n-1 次适合交换成本较高的场景。3. 直接插入排序Insertion Sort核心思想把数组分成“已排序”和“未排序”两部分每次把未排序的第一个元素插入到已排序部分的正确位置。3.1 代码实现void InsertionSort(vectorint 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.2 复杂度与稳定性指标说明最好时间复杂度O(n)已经有序平均 / 最坏时间复杂度O(n²)空间复杂度O(1)稳定性稳定特点对接近有序的数组效率很高实际中常作为快速排序的优化手段小数组用插入排序。4. 三种简单排序对比排序方法最好时间平均时间最坏时间空间稳定性特点冒泡排序O(n)O(n²)O(n²)O(1)稳定可优化提前结束选择排序O(n²)O(n²)O(n²)O(1)不稳定交换次数少插入排序O(n)O(n²)O(n²)O(1)稳定对近乎有序数据效率高5. 完整测试代码#include iostream #include vector using namespace std; void printArray(const vectorint arr) { for (int x : arr) cout x ; cout endl; } int main() { vectorint arr1 {49, 38, 65, 97, 76, 13, 27, 49}; vectorint arr2 arr1; vectorint arr3 arr1; cout 原数组; printArray(arr1); BubbleSort(arr1); cout 冒泡排序后; printArray(arr1); SelectionSort(arr2); cout 选择排序后; printArray(arr2); InsertionSort(arr3); cout 插入排序后; printArray(arr3); return 0; }运行结果原数组49 38 65 97 76 13 27 49 冒泡排序后13 27 38 49 49 65 76 97 选择排序后13 27 38 49 49 65 76 97 插入排序后13 27 38 49 49 65 76 976. 总结与思考这三种排序虽然效率不高但思想非常重要冒泡相邻比较与交换。选择每轮选最值。插入通过移动维护有序前缀。结合《C Primer Plus》的思考全部使用引用传递vectorint避免不必要的拷贝对应书中关于参数传递效率的讨论。插入排序中的元素后移体现了对数组连续内存特性的利用。下一篇将继续第9章讲解性能更好的希尔排序和堆排序。