三大基本排序算法：冒泡排序、直接插入排序、直接选择排序

三大基本排序算法冒泡排序、直接插入排序、直接选择排序冒泡排序、直接插入排序和直接选择排序是排序算法中最基础的三种虽然时间复杂度都是 O(n²)但它们各自的思想、实现细节和适用场景有着本质区别。本文从算法思想、代码实现、复杂度分析到稳定性逐一拆解适合初学者建立对排序算法的系统认知。冒泡排序算法思想冒泡排序的核心是相邻比较、逐轮冒泡每一轮从数组头部开始依次比较相邻的两个元素如果顺序不对就交换它们。一轮下来当前未排序部分的最大值就会被推到它应该在的位置——就像气泡从水中浮出一样。具体步骤从第一个元素开始依次比较相邻的两个元素arr[j]和arr[j1]。如果arr[j] arr[j1]升序则交换它们。每一轮遍历后未排序部分的最大元素被放到了正确位置当前轮的末尾。下一轮缩小范围继续对剩余元素重复上述过程。如果某一轮没有发生任何交换说明数组已经有序可以提前结束。以一个数组[5, 3, 8, 1, 2]为例第一轮冒泡过程初始[5, 3, 8, 1, 2] 53 交换 → [3, 5, 8, 1, 2] 58 不换 → [3, 5, 8, 1, 2] 81 交换 → [3, 5, 1, 8, 2] 82 交换 → [3, 5, 1, 2, 8] ← 8 归位代码实现voidswap(int*a,int*b){inttmp*a;*a*b;*btmp;}voidBubbleSort(int*arr,intn){for(inti0;in;i){intflag0;// 每轮重置标记是否发生交换for(intj0;jn-i-1;j){if(arr[j]arr[j1]){swap(arr[j],arr[j1]);flag1;}}if(flag0)// 本轮没有交换已经有序{break;}}}优化点flag变量用于检测某一轮是否发生了交换。如果没有发生交换说明数组已经有序可以提前结束循环。这使得最好情况下数组已经有序时间复杂度降为 O(n)。复杂度与稳定性指标说明最好时间复杂度O(n) — 数组已经有序一轮扫描后 flag0 直接退出最坏时间复杂度O(n²) — 数组逆序每轮都要交换平均时间复杂度O(n²)空间复杂度O(1) — 原地排序仅用常量级额外空间稳定性稳定— 只有arr[j] arr[j1]时才交换相等元素不会互换位置直接插入排序算法思想直接插入排序模拟的是打扑克牌时整理手牌的过程手里已经有一部分排好序的牌有序序列每拿到一张新牌待插入元素就从后往前扫描已排序部分找到合适的位置插入。具体步骤将第一个元素视为已排序序列。取出下一个元素作为待插入元素tmp。在已排序序列中从后向前扫描如果已排序元素大于tmp则将该元素后移一位。找到第一个不大于tmp的位置将tmp插入其后。重复步骤 2-4直到所有元素处理完毕。以数组[5, 3, 8, 1, 2]为例i0: [5 | 3, 8, 1, 2] 5视为已排序 i1: [3, 5 | 8, 1, 2] 3插入到5前面 i2: [3, 5, 8 | 1, 2] 8不变已在正确位置 i3: [1, 3, 5, 8 | 2] 1一直移动到最前面 i4: [1, 2, 3, 5, 8] 2插入到3前面代码实现voidInsertSort(int*arr,intn){for(inti0;in-1;i){intendi;// 已排序部分的最后一个位置inttmparr[end1];// 待插入的元素while(end0){if(arr[end]tmp){arr[end1]arr[end];// 比tmp大的元素后移end--;}else{break;// 找到插入位置}}arr[end1]tmp;// 插入到正确位置}}关键细节外层循环条件是i n - 1因为当i n-2时取arr[n-1]作为最后一个待插入元素。while循环的终止条件是end 0当end减到-1时说明tmp比所有已排序元素都小插入到数组最前面。复杂度与稳定性指标说明最好时间复杂度O(n) — 数组已经有序内层 while 每次只比较一次就 break最坏时间复杂度O(n²) — 数组逆序每个元素都要移到最前面平均时间复杂度O(n²)空间复杂度O(1) — 原地排序稳定性稳定— 只有arr[end] tmp时才后移相等元素不跨越直接选择排序算法思想直接选择排序的核心是每轮选出最值放到两端每一轮在未排序区间中找到最小值和最大值将最小值放到区间开头最大值放到区间末尾然后缩小区间继续。本文展示的是双向优化版本每轮同时选出最小值和最大值比传统单向选择排序少一半的遍历轮数。具体步骤设定左右边界begin 0end n - 1。在[begin, end]范围内遍历记录最小值下标mini和最大值下标maxi。将arr[mini]与arr[begin]交换将arr[maxi]与arr[end]交换。beginend--缩小区间。重复步骤 2-4直到begin end。以数组[5, 3, 8, 1, 2]为例[5, 3, 8, 1, 2] begin0, end4, mini3(值1), maxi2(值8) 交换mini↔begin, maxi↔end → [1, 3, 2, 5, 8] [1, 3, 2, 5, 8] begin1, end3, mini2(值2), maxi3(值5) 交换mini↔begin, maxi↔end → [1, 2, 3, 5, 8] begin2, end2 → 结束代码实现voidSelectSort(int*arr,intn){intbegin0,endn-1;while(beginend){intmaxibegin;intminibegin;// 在 [begin, end] 中同时找最大值和最小值的下标for(intibegin1;iend;i){if(arr[i]arr[maxi]){maxii;}if(arr[i]arr[mini]){minii;}}// 关键如果 begin 位置恰好是最大值第一次交换会把它移走// 需要让 maxi 指向最大值被移到的位置即原来的 mini 位置if(beginmaxi){maximini;}swap(arr[mini],arr[begin]);// 最小值放到区间头swap(arr[maxi],arr[end]);// 最大值放到区间尾begin;end--;}}swap 顺序的陷阱这是选择排序中最容易出错的细节。我们先交换mini和begin但如果begin恰好是maxi即最大值就在区间头第一次交换后最大值已经被移到了原来mini的位置此时maxi仍然指向begin就会出错。所以需要先判断begin maxi将maxi更新为mini确保第二次交换时maxi指向真正的最大值。复杂度与稳定性指标说明最好时间复杂度O(n²) — 即使数组有序仍然需要完整遍历最坏时间复杂度O(n²)平均时间复杂度O(n²)空间复杂度O(1) — 原地排序稳定性不稳定— 交换非相邻元素会打乱相等元素的相对顺序选择排序是三种算法中唯一不稳定的排序。例如数组[5, 8, 5, 2]第一个 5 会和 2 交换导致两个 5 的相对顺序发生改变。三种排序对比冒泡排序直接插入排序直接选择排序最好时间O(n)O(n)O(n²)最坏时间O(n²)O(n²)O(n²)平均时间O(n²)O(n²)O(n²)空间O(1)O(1)O(1)稳定性稳定稳定不稳定比较次数多相邻比较少提前终止多必须扫完移动/交换次数多每次比较可能交换多元素逐个后移少每轮最多2次交换适用场景小规模数据教学入门基本有序的数据小规模对交换次数敏感的场景总结冒泡排序思路最直观适合入门理解排序的基本操作比较和交换。通过flag优化可以在有序时达到 O(n)。直接插入排序模拟理牌过程对于基本有序的数据表现极好接近 O(n)是小规模数据和部分排序场景的首选。直接选择排序交换次数最少但无论如何都要 O(n²) 的比较次数且不稳定。双向优化可以减少遍历轮数但不改变时间复杂度级别。三种算法虽然在实际项目中很少直接使用规模稍大就会被快排、归并等 O(n log n) 算法替代但它们是理解更复杂排序算法的基石也是面试中的高频考点。