五大经典排序算法：插入、希尔、冒泡、选择、堆排序全攻略-程序员充电站

五大经典排序算法全攻略：插入、希尔、冒泡、选择、堆排序

这五个算法是学习排序算法时最常遇到的“入门+进阶”组合，它们在思想、复杂度、稳定性、适用场景上各有特点，非常适合对比学习。

下面按从简单到相对复杂的顺序详细讲解，并给出清晰对比表、核心思想、代码实现（Java）、关键性质和真实使用场景。

一、五大排序算法对比表（强烈建议背下来）

排序算法	时间复杂度（最好/平均/最坏）	空间复杂度	稳定性	原地排序	思想关键词	最佳适用场景
插入排序	O(n) / O(n²) / O(n²)	O(1)	稳定	是	像打扑克牌插牌	小规模数据、近乎有序的数组
希尔排序	O(n log n) ~ O(n¹·³) / O(n²)	O(1)	不稳定	是	插入排序 + 分组缩小增量	中等规模数据、部分有序
冒泡排序	O(n) / O(n²) / O(n²)	O(1)	稳定	是	相邻元素两两比较交换	教学演示、极小规模数据
选择排序	O(n²) / O(n²) / O(n²)	O(1)	不稳定	是	每轮选最小/最大放前面	交换次数要求极少的情况
堆排序	O(n log n) / O(n log n) / O(n log n)	O(1)	不稳定	是	构建大/小顶堆 + 堆顶交换	需要稳定 O(n log n) 且空间紧张的场景

二、逐个详细讲解

1. 插入排序（Insertion Sort）

核心思想：
把数组分为“已排序”和“未排序”两部分，每轮从未排序部分取一个元素，插入到已排序部分的正确位置（类似打扑克牌插牌）。

Java 实现（最清晰版本）

publicvoidinsertionSort(int[]arr){intn=arr.length;for(inti=1;i<n;i++){intkey=arr[i];// 当前要插入的数intj=i-1;// 将大于 key 的元素向后移动while(j>=0&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;// 插入到正确位置}}

稳定性：稳定（相同元素相对顺序不变）

优化点：可以用二分查找优化查找插入位置（→ 折半插入排序）

2. 希尔排序（Shell Sort）

核心思想：
插入排序的升级版，先进行大跨度分组插入排序，逐渐缩小分组间距（增量），最后变成增量为1的普通插入排序。

增量序列（常见几种）：

原始 Shell：n/2, n/4, …, 1
Hibbard：2^k - 1
Sedgewick：… 推荐使用较优序列

Java 实现（经典 /2 序列）

publicvoidshellSort(int[]arr){intn=arr.length;// 增量从大到小for(intgap=n/2;gap>0;gap/=2){// 对每个分组做插入排序for(inti=gap;i<n;i++){inttemp=arr[i];intj=i;while(j>=gap&&arr[j-gap]>temp){arr[j]=arr[j-gap];j-=gap;}arr[j]=temp;}}}

特点：

打破了 O(n²) 的魔咒（平均远好于 O(n²)）
不稳定（跨组交换导致）

3. 冒泡排序（Bubble Sort）

核心思想：
相邻元素两两比较，如果顺序错误就交换，每轮把最大的元素“冒泡”到末尾。

Java 实现（带优化）

publicvoidbubbleSort(int[]arr){intn=arr.length;booleanswapped;for(inti=0;i<n-1;i++){swapped=false;// 每轮比较到未排序部分的末尾for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){// 交换inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;swapped=true;}}// 如果本轮没有交换，说明已经有序if(!swapped)break;}}

优化：加swapped标志位可提前结束

4. 选择排序（Selection Sort）

核心思想：
每轮从未排序部分选出最小（或最大）的元素，放到已排序部分的末尾。

Java 实现

publicvoidselectionSort(int[]arr){intn=arr.length;for(inti=0;i<n-1;i++){intminIndex=i;// 在未排序部分找最小for(intj=i+1;j<n;j++){if(arr[j]<arr[minIndex]){minIndex=j;}}// 交换到正确位置if(minIndex!=i){inttemp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=temp;}}}

特点：交换次数最少（最多 n-1 次）

5. 堆排序（Heap Sort）

核心思想：
利用二叉堆（通常是大顶堆）特性：

先把数组建成大顶堆
每次把堆顶（最大元素）放到数组末尾
调整剩余堆，重复直到排序完成

Java 实现（大顶堆）

publicvoidheapSort(int[]arr){intn=arr.length;// 建堆（从第一个非叶子节点开始）for(inti=n/2-1;i>=0;i--){heapify(arr,n,i);}// 依次取出堆顶放到末尾for(inti=n-1;i>0;i--){// 交换堆顶和末尾swap(arr,0,i);// 调整剩余堆heapify(arr,i,0);}}// 堆调整（大顶堆）privatevoidheapify(int[]arr,intn,inti){intlargest=i;intleft=2*i+1;intright=2*i+2;if(left<n&&arr[left]>arr[largest]){largest=left;}if(right<n&&arr[right]>arr[largest]){largest=right;}if(largest!=i){swap(arr,i,largest);heapify(arr,n,largest);// 递归向下}}privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}