1 对比总览
| 排序算法 | 核心思想 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 插入排序 | 将待排序元素插入到已有序序列的合适位置 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 折半插入排序 | 用折半查找优化插入位置的查找过程 | O(n log n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 希尔排序 | 分组插入排序，逐步缩小增量 | O(n) | O(n²) | O(n^1.3~n²) | O(1) | ❌ 不稳定 |
| 冒泡排序 | 相邻元素两两比较，将较大元素逐步"冒泡"到末尾 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 快速排序 | 选取基准，分治递归地将序列分为小于和大于基准的两部分 | O(n log n) | O(n²) | O(n log n) | O(log n)~O(n) | ❌ 不稳定 |
| 简单选择排序 | 每趟选择未排序部分的最小元素放到已排序末尾 | 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) | O(n log n) | O(n log n) | O(n) | ✅ 稳定 |
| 基数排序 | 按位（个/十/百位）依次进行分配和收集 | O(d·(n+k)) | O(d·(n+k)) | O(d·(n+k)) | O(n+k) | ✅ 稳定 |
注：基数排序中，d 为最大位数，k 为基数（如十进制 k=10）。
2 详细说明
2.1 插入排序
核心思想：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，在已排序部分从后往前依次比较，找到合适位置插入。
适用场景：数据量小（n < 50）或数据基本有序时效率很高。
特点：实现简单，稳定，在接近有序时性能接近 O(n)。
2.2 折半插入排序
核心思想：在插入排序的基础上，利用折半查找（二分查找）在已排序序列中快速定位插入位置，减少比较次数。
特点：相比直接插入排序减少了比较次数，但移动次数不变，整体时间复杂度仍为 O(n²)。
2.3 希尔排序
核心思想：将序列按一定增量分组，对每组进行插入排序；逐步减小增量，当增量为 1 时整个序列基本有序，最后做一次完整插入排序。
增量序列：常见的有 Hibbard 增量（2^k-1）、Sedgewick 增量等，不同增量序列影响时间复杂度。
特点：第一个突破 O(n²) 的排序算法，是插入排序的改进版。
2.4 冒泡排序
核心思想：从前往后依次比较相邻元素，若逆序则交换，每趟将当前未排序部分的最大元素"冒泡"到末尾。
优化方案：设置标志位，若一趟遍历没有发生交换说明已有序，可提前结束。
特点：简单直观，速度较慢，适合教学场景。
2.5 快速排序
核心思想：选择一个基准元素（pivot），将序列分成两部分——小于等于基准的在左边，大于基准的在右边，然后递归地对左右两部分排序。
最坏情况：每次选择的基准恰好是最大或最小元素，退化为 O(n²)；可通过随机选取基准或三数取中法优化。
特点：实际应用中最快的排序算法之一，C 标准库的
qsort即采用此算法。
2.6 简单选择排序
核心思想：每趟在未排序部分中找到最小（或最大）元素，将其与未排序部分的第一个元素交换。
特点：比较次数始终为 O(n²)，与初始序列无关；但移动次数较少。
2.7 堆排序
核心思想：将序列构建成一个大顶堆（或小顶堆），每次取出堆顶元素（最大值或最小值），将堆尾元素移到堆顶后调整堆，重复 n-1 次。
特点：始终保持在 O(n log n) 的时间复杂度，不受初始序列影响；但不稳定。
2.8 归并排序
核心思想：采用分治策略，将序列递归地二分至单个元素，然后逐层合并两个有序子序列。
实现方式：分为自上而下的递归实现和自下而上的迭代实现。
特点：稳定排序，效率稳定在 O(n log n)，但需要 O(n) 的额外空间。
2.9 基数排序
核心思想：不直接比较元素大小，而是按位数（个位、十位、百位…）依次进行分配（入桶）和收集（出桶）。
实现方式：
LSD（Least Significant Digit）：从最低位开始排序
MSD（Most Significant Digit）：从最高位开始排序
特点：非比较排序，适用于整数或固定长度字符串，时间复杂度为线性。
