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

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

冒泡排序、直接插入排序和直接选择排序是排序算法中最基础的三种，虽然时间复杂度都是 O(n²)，但它们各自的思想、实现细节和适用场景有着本质区别。本文从算法思想、代码实现、复杂度分析到稳定性逐一拆解，适合初学者建立对排序算法的系统认知。

冒泡排序

算法思想

冒泡排序的核心是"相邻比较、逐轮冒泡"：每一轮从数组头部开始，依次比较相邻的两个元素，如果顺序不对就交换它们。一轮下来，当前未排序部分的最大值就会被"推"到它应该在的位置——就像气泡从水中浮出一样。

具体步骤

1. 从第一个元素开始，依次比较相邻的两个元素arr[j]和arr[j+1]。
2. 如果arr[j] > arr[j+1]（升序），则交换它们。
3. 每一轮遍历后，未排序部分的最大元素被放到了正确位置（当前轮的末尾）。
4. 下一轮缩小范围，继续对剩余元素重复上述过程。
5. 如果某一轮没有发生任何交换，说明数组已经有序，可以提前结束。

以一个数组[5, 3, 8, 1, 2]为例，第一轮冒泡过程：

初始：[5, 3, 8, 1, 2] 5>3 交换 → [3, 5, 8, 1, 2] 5<8 不换 → [3, 5, 8, 1, 2] 8>1 交换 → [3, 5, 1, 8, 2] 8>2 交换 → [3, 5, 1, 2, 8] ← 8 归位

代码实现

voidswap(int*a,int*b){inttmp=*a;*a=*b;*b=tmp;}voidBubbleSort(int*arr,intn){for(inti=0;i<n;i++){intflag=0;// 每轮重置，标记是否发生交换for(intj=0;j<n-i-1;j++){if(arr[j]>arr[j+1]){swap(&arr[j],&arr[j+1]);flag=1;}}if(flag==0)// 本轮没有交换，已经有序{break;}}}

优化点：flag变量用于检测某一轮是否发生了交换。如果没有发生交换，说明数组已经有序，可以提前结束循环。这使得最好情况下（数组已经有序）时间复杂度降为 O(n)。

复杂度与稳定性

直接插入排序

算法思想

直接插入排序模拟的是"打扑克牌时整理手牌"的过程：手里已经有一部分排好序的牌（有序序列），每拿到一张新牌（待插入元素），就从后往前扫描已排序部分，找到合适的位置插入。

具体步骤

1. 将第一个元素视为已排序序列。
2. 取出下一个元素作为待插入元素tmp。
3. 在已排序序列中从后向前扫描，如果已排序元素大于tmp，则将该元素后移一位。
4. 找到第一个不大于tmp的位置，将tmp插入其后。
5. 重复步骤 2-4，直到所有元素处理完毕。

以数组[5, 3, 8, 1, 2]为例：

i=0: [5 | 3, 8, 1, 2] 5视为已排序 i=1: [3, 5 | 8, 1, 2] 3插入到5前面 i=2: [3, 5, 8 | 1, 2] 8不变，已在正确位置 i=3: [1, 3, 5, 8 | 2] 1一直移动到最前面 i=4: [1, 2, 3, 5, 8] 2插入到3前面

代码实现

voidInsertSort(int*arr,intn){for(inti=0;i<n-1;i++){intend=i;// 已排序部分的最后一个位置inttmp=arr[end+1];// 待插入的元素while(end>=0){if(arr[end]>tmp){arr[end+1]=arr[end];// 比tmp大的元素后移end--;}else{break;// 找到插入位置}}arr[end+1]=tmp;// 插入到正确位置}}

关键细节：

• 外层循环条件是i < n - 1，因为当i = n-2时取arr[n-1]作为最后一个待插入元素。
• while循环的终止条件是end >= 0，当end减到-1时说明tmp比所有已排序元素都小，插入到数组最前面。

复杂度与稳定性

直接选择排序

算法思想

直接选择排序的核心是"每轮选出最值，放到两端"：每一轮在未排序区间中找到最小值和最大值，将最小值放到区间开头，最大值放到区间末尾，然后缩小区间继续。

本文展示的是双向优化版本，每轮同时选出最小值和最大值，比传统单向选择排序少一半的遍历轮数。

具体步骤

1. 设定左右边界begin = 0，end = n - 1。
2. 在[begin, end]范围内遍历，记录最小值下标mini和最大值下标maxi。
3. 将arr[mini]与arr[begin]交换，将arr[maxi]与arr[end]交换。
4. begin++，end--，缩小区间。
5. 重复步骤 2-4，直到begin >= end。

以数组[5, 3, 8, 1, 2]为例：

[5, 3, 8, 1, 2] begin=0, end=4, mini=3(值1), maxi=2(值8) 交换mini↔begin, maxi↔end → [1, 3, 2, 5, 8] [1, 3, 2, 5, 8] begin=1, end=3, mini=2(值2), maxi=3(值5) 交换mini↔begin, maxi↔end → [1, 2, 3, 5, 8] begin=2, end=2 → 结束

代码实现

voidSelectSort(int*arr,intn){intbegin=0,end=n-1;while(begin<end){intmaxi=begin;intmini=begin;// 在 [begin, end] 中同时找最大值和最小值的下标for(inti=begin+1;i<=end;i++){if(arr[i]>arr[maxi]){maxi=i;}if(arr[i]<arr[mini]){mini=i;}}// 关键：如果 begin 位置恰好是最大值，第一次交换会把它移走// 需要让 maxi 指向最大值被移到的位置（即原来的 mini 位置）if(begin==maxi){maxi=mini;}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指向真正的最大值。

复杂度与稳定性

选择排序是三种算法中唯一不稳定的排序。例如数组[5, 8, 5, 2]，第一个 5 会和 2 交换，导致两个 5 的相对顺序发生改变。

三种排序对比

总结

• 冒泡排序：思路最直观，适合入门理解排序的基本操作（比较和交换）。通过flag优化可以在有序时达到 O(n)。
• 直接插入排序：模拟理牌过程，对于基本有序的数据表现极好（接近 O(n)），是小规模数据和部分排序场景的首选。
• 直接选择排序：交换次数最少，但无论如何都要 O(n²) 的比较次数，且不稳定。双向优化可以减少遍历轮数，但不改变时间复杂度级别。

三种算法虽然在实际项目中很少直接使用（规模稍大就会被快排、归并等 O(n log n) 算法替代），但它们是理解更复杂排序算法的基石，也是面试中的高频考点。