五大经典排序算法全攻略：插入、希尔、冒泡、选择、堆排序
这五个算法是学习排序算法时最常遇到的“入门+进阶”组合，它们在思想、复杂度、稳定性、适用场景上各有特点，非常适合对比学习。
下面按从简单到相对复杂的顺序详细讲解，并给出清晰对比表、核心思想、代码实现（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;}三、总结与选择建议
快速记忆口诀：
- 小数据 / 近乎有序 →插入排序
- 中等数据 + 想简单优化 →希尔排序
- 教学演示 / 理解交换 →冒泡
- 交换次数最少 →选择排序
- 稳定 O(n log n) + 空间 O(1) →堆排序
面试常问对比问题：
- 哪些是稳定的？（插入、冒泡）
- 哪些一定是 O(n²)？（冒泡、插入、选择）
- 为什么堆排序不稳定？
- 希尔排序为什么比插入快很多？
- 实际项目中你会用哪种排序？为什么？
如果你想看这五种算法的动画演示对比、稳定性动画、不同数据规模下的性能实测，或者需要其他语言的实现（Python、C++、Go等），可以告诉我，我继续补充。
