前置理解数组 一排格子下标从 0 开始目标从小到大排序temp 临时盒子用来交换数字防止数字被覆盖丢失。一、冒泡排序小故事相邻两个人比身高高的往后挪大个子像泡泡一样慢慢浮到队伍最后。例子[3, 1, 4, 2]第一轮 0 号 3 和 1 号 1 比 → 交换 →[1,3,4,2]1 号 3 和 2 号 4 比 → 不换 2 号 4 和 3 号 2 比 → 交换 →[1,3,2,4]✅本轮结束最大的 4 已经浮到最后不再参与后面比较。第二轮只对比前 3 个[1,3,2,4]0 号 1 和 1 号 3不换 1 号 3 和 2 号 2交换 →[1,2,3,4]✅3 浮到倒数第二个。第三轮只剩前 2 个对比不用交换。文字示意图原始队伍3 1 4 2 第一轮 1 3 2 [4] ←4排好右边有序 第二轮 1 2 [3 4] ←3排好 第三轮 1 [2 3 4] ←全部有序一句话两两对比大个子一步步飘到末尾。1. 通俗原理相邻两个数字对比左边大就交换每一轮把最大数 “浮” 到数组最后后面排好的数字不再参与比较。有序区域数组右边。2. 完整代码#includestdio.h int main() { int arr[10] {3,8,4,6,5,1,2,7,9,1}; int len sizeof(arr) / sizeof(arr[0]); for(int j 0; j len - 1; j) { for(int i 0; i len - 1 - j; i) { if(arr[i] arr[i 1]) { int temp arr[i]; arr[i] arr[i 1]; arr[i 1] temp; } } } printf(冒泡排序结果); for(int i 0; i len; i) { printf(%d , arr[i]); } return 0; }3. 特点逻辑最简单交换次数最多数据量大效率低无论有序无序都要多次对比。二、选择排序小故事从队伍乱的一侧找到全场最矮的人直接拉到队伍最前面站好。例子[3, 1, 4, 2]原始[3, 1, 4, 2]第一轮在全部 4 个人里找最矮的是 1下标 1和最前面 3 交换 →[1, 3, 4, 2]✅0 号位置排好。第二轮剩下后面 3 个人[3,4,2]找最矮的 2下标 3和下标 1 的 3 交换 →[1, 2, 4, 3]✅1 号位置排好。第三轮剩下后面 2 个人[4,3]找最矮 3交换 →[1, 2, 3, 4]文字示意图原始队伍 3 1 4 2 第一轮[1] 3 4 2 ←最矮的1放到最左边左边有序 第二轮[1 2] 4 3 ←剩下里面最矮的2放到左边 第三轮[1 2 3] 4 ←全部有序一句话每次找全场最小值直接放到左边空位一轮只交换一次。1. 通俗原理左边是有序区右边无序区每一轮在无序区找到最小值的下标一轮结束后直接和当前左边位置交换一轮最多交换 1 次。有序区域数组左边。2. 完整代码#includestdio.h int main() { int arr[10] {1,8,6,4,5,7,11,32,10,20}; int len sizeof(arr) / sizeof(arr[0]); for(int j 0; j len - 1; j) { int minIndex j; for(int i j 1; i len; i) { if(arr[i] arr[minIndex]) { minIndex i; } } int temp arr[j]; arr[j] arr[minIndex]; arr[minIndex] temp; } printf(选择排序结果); for(int i 0; i len; i) { printf(%d , arr[i]); } return 0; }3. 特点交换极少固定循环次数数组提前有序也不会减少循环只找最小下标一轮只换位一次。适合交换成本很高的场景交换一次数据很耗时选择排序虽然比较次数多但一轮只交换一次能减少交换操作。三、插入排序小故事摸扑克牌。手里的牌已经排好桌上拿一张新牌插到手里合适位置。例子[3, 1, 4, 2]手里一开始拿第一张[3]有序 拿第二张 11 比 3 小插到 3 前面 →[1,3]拿第三张 44 比 3 大放末尾 →[1,3,4]拿第四张 2依次和前面对比4、3 都比 2 大全部往后挪空出位置放 2 →[1,2,3,4]文字示意图初始手牌[3] 桌上剩余1,4,2 拿1 [1,3] 桌上剩余4,2 拿4 [1,3,4] 桌上剩余2 拿2 [1,2,3,4]✅一句话拿新数字插入左边已经排好的队伍。数组越接近有序越快。1. 通俗原理像摸扑克牌第一个数字默认有序依次拿后面每一个数字往左边有序区间插入比它大的数字全部后移腾出空位放入。有序区域数组左边。2. 完整代码#includestdio.h int main() { int arr[10] {1,3,8,4,10,5,6,10,7,9}; int len sizeof(arr) / sizeof(arr[0]); for(int j 1; j len; j) { int temp arr[j]; int i j - 1; while(i 0 arr[i] temp) { arr[i 1] arr[i]; i--; } arr[i 1] temp; } printf(插入排序结果); for(int i 0; i len; i) { printf(%d , arr[i]); } return 0; }3. 特点数组越接近有序速度越快没有频繁交换只有数字移位日常小规模数据很实用。四、计数排序俗称桶排序备注计数排序≠桶排序只是原理相似很多教材会俗称桶排序严格来说二者是不同算法答题尽量写计数排序。小故事一排编号的空水桶编号就是数字。读到数字几就在几号桶放一个小球。最后从小到大看桶桶里有几个球就输出几次桶编号。例子[3, 1, 4, 2, 2]桶编号0 1 2 3 4放小球 数字 3 → 3 号桶 1 数字 1 → 1 号桶 1 数字 4 → 4 号桶 1 数字 2 → 2 号桶 1 数字 2 → 2 号桶 1桶状态 桶 00 个 桶 11 个 桶 22 个 桶 31 个 桶 41 个从小到大读桶12234。一句话不用互相比较数字靠桶计数。缺点数字跨度大就要准备超多空桶浪费空间。1. 通俗原理不用对比大小用数组下标当 “桶”数字是几就几号桶计数最后从小到大遍历桶输出天然有序只适合小范围非负整数。2. 完整基础代码#includestdio.h int main() { int arr[8] {5,2,9,2,1,5,7,3}; int len sizeof(arr) / sizeof(arr[0]); int max arr[0]; for(int i 1; i len; i) { if(arr[i] max) max arr[i]; } int bucket[100] {0}; for(int i 0; i len; i) { bucket[arr[i]]; } printf(计数排序结果); for(int i 0; i max; i) { while(bucket[i] 0) { printf(%d , i); bucket[i]--; } } return 0; }3. 拓展例题找出只出现一次的数字#includestdio.h int main() { int n; printf(请输入数组长度); scanf(%d, n); int arr[100]; for(int i 0; i n; i) { printf(输入第%d个数字, i 1); scanf(%d, arr[i]); } int brr[1000] {0}; for(int i 0; i n; i) { brr[arr[i]]; } printf(只出现一次的数字为); for(int i 0; i 1000; i) { if(brr[i] 1) { printf(%d , i); } } return 0; }4. 特点速度最快无交换无对比只能排非负整数数字跨度大时极度浪费内存。不同场景选哪种排序数据量小、代码简单好写 → 冒泡排序交换成本很高交换一次数据很耗时 → 选择排序数据大部分已经有序或边增加数据边排序 → 插入排序非负整数数值范围不大例如成绩 0~100 → 计数排序时间复杂度与稳定性【拓展内容可跳过】稳定排序值相同元素排序前后相对顺序不变。 O (nk)n 是数据个数k 是数值范围。排序最好时间复杂度最坏时间复杂度平均复杂度是否稳定排序冒泡排序O(n)O(n²)O(n²)稳定选择排序O(n²)O(n²)O(n²)不稳定插入排序O(n)O(n²)O(n²)稳定计数排序O(nk)O(nk)O(nk)稳定这里没有详细讲解看不懂是正常的后续数据结构课程会深入学习。