五大排序算法完全详解(QuickSort / MergeSort / HeapSort / InsertionSort / ShellSort)
五大排序算法完全详解(QuickSort / MergeSort / HeapSort / InsertionSort / ShellSort)
目录
由来与发展(Timeline)
总览比较表
插入排序(Insertion Sort)
希尔排序(Shell Sort)
快速排序(Quick Sort)
归并排序(Merge Sort)
堆排序(Heap Sort)
实战建议:何时选哪种排序 & 基准方法
附:C# 基准测试模板与常见调试技巧
1. 由来与发展(Timeline)
插入排序(Insertion Sort):最古老的排序思想之一,正好像你手里理扑克牌,古老但在小规模/近似有序场景中仍然强力。
归并排序(Merge Sort):1945 年由 John von Neumann 首次提出(分治思想早已存在,但他给出了数组/列表合并的形式化实现),是稳定排序的经典代表。
快速排序(Quick Sort):1960 年由 C. A. R. Hoare 提出,基于分区的分治法,工程上常用且常数项小,被命名为“快速”并非绝对最快,而是早期比其他方法快很多。
希尔排序(Shell Sort):1959 年由 Donald Shell 提出,是插入排序的“加速版”。
堆排序(Heap Sort):1964 年由 J. W. J. Williams 提出,使用二叉堆(完全二叉树)作为核心数据结构。
这些算法在学术与工程界长期发展出大量变体与工程化优化(如三路快排、随机枢轴、迭代归并、自底向上归并、线性建堆、不同 gap 序列的 Shell 排序等)。
2. 总览比较表
算法 | 平均时间 | 最坏时间 | 最优时间 | 额外空间 | 稳定性 | 适用场景/点评 |
---|---|---|---|---|---|---|
插入(Insertion) | O(n²) | O(n²) | O(n) | O(1) | ✔ 稳定 | 小数组、几乎有序时最好,常用于快速排序/归并排序的小区间优化 |
希尔(Shell) | 依 gap 而定(常 ~O(n^1.3)) | 最坏 O(n²) | 视 gap | O(1) | ✖ 不稳定 | 插入优化;中等规模数组内存敏感时优选 |
快速(QuickSort) | O(n log n) | O(n²) | O(n log n) | O(log n) 递归栈 | ✖ 不稳定 | 常用、最快的候选(对随机数据);需防最坏情况 |
归并(MergeSort) | O(n log n) | O(n log n) | O(n log n) | O(n) | ✔ 稳定 | 需要稳定、外部排序或链表排序时首选 |
堆(HeapSort) | O(n log n) | O(n log n) | O(n log n) | O(1) | ✖ 不稳定 | 要原地(O(1) 额外)且保证最坏情形时用 |
3. 插入排序(Insertion Sort)
核心思想
逐一把当前元素插入到左边已排序的序列中,保持左区间有序。就如理扑克牌。
逐步示例
[4, 2, 7, 1]
:
i=1 插入 2 →
[2,4,7,1]
i=2 插入 7 →
[2,4,7,1]
i=3 插入 1 →
[1,2,4,7]
public static void InsertionSort(int[] nums) { for (int i = 1; i < nums.Length; i++) { int key = nums[i]; int j = i - 1; while (j >= 0 && nums[j] > key) { nums[j + 1] = nums[j]; j--; } nums[j + 1] = key; } }
复杂度
最好:O(n)(已近似有序)
平均/最坏:O(n²)
空间:O(1)
优点
实现简单、稳定
小数组或基本有序数据时速度很快
缺点 / 应用场景
大数组会很慢
常作为“优化工具”:当递归排序算法拆分到小长度(如 ≤ 16 或 ≤ 32)时,用插入排序处理小段通常更快(降低常数开销)。
4. 希尔排序(Shell Sort)
核心思想
先用较大步长(gap)做“分组插入排序”,逐步缩小 gap,最后 gap=1 时完成常规插入排序。通过“跳跃”让远距离的元素先移动到合理区域,从而减少总移动。
常见 gap 序列
最简单:
gap = n/2, gap/=2
(Shell 原始)Knuth:
gap = gap*3 + 1
形式(生成序列)Ciura(实测较好):
701,301,132,57,23,10,4,1
(常被用于实践)
public static void ShellSort(int[] nums) { int n = nums.Length; // 常见简化 gap 序列(可换为 Ciura 序列) for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = nums[i]; int j = i; while (j - gap >= 0 && nums[j - gap] > temp) { nums[j] = nums[j - gap]; j -= gap; } nums[j] = temp; } } }
复杂度
取决于 gap 序列:常见实践约 O(n^1.3 ~ n^1.5),最坏可达 O(n²)。
优点/缺点
原地(O(1) 额外)且实现简单
不稳定
对于中等规模数据往往优于插入排序
5. 快速排序(Quick Sort)
历史小记
1960 年由 Hoare 提出,分区 + 递归的思想让它在实践中成为极为高效的通用排序方法。多种工程优化(随机枢轴、三路划分、三数取中、小段插入排序)让它既快又稳健。
核心思想
选定一个枢轴(pivot),将所有元素分为 <=pivot
的一组和 > pivot
的一组(不同实现在等号归属上略有差别),然后递归排序两边。关键在于如何分区与如何选枢轴。
常见分区方法
Hoare 分区(移动交换两侧指针)——交换次数少
Lomuto 分区(基于单指针)——实现简单但交换多
三路(Dutch National Flag)分区——处理大量重复元素时优势明显
选枢轴策略
固定位置(首/尾/中)——简单但有退化风险
随机化枢轴(随机选)——概率上避免退化
三数取中(median-of-three)——在常见有序或近有序情况下表现更稳健
稳定性/空间/时间
平均 O(n log n),最坏 O(n²)(若每次分区极不均衡)
原地(就地)实现常见,额外空间 O(log n)(递归栈)
不稳定
public static void QuickSort(int[] array, int left, int right) { if (left >= right) return; // 终止条件 int temp = array[left]; // 枢轴 int tempLeft = left; int tempRight = right; while (tempLeft < tempRight) { while (tempLeft < tempRight && array[tempRight] >= temp) tempRight--; if (tempLeft < tempRight) array[tempLeft] = array[tempRight]; while (tempLeft < tempRight && array[tempLeft] <= temp) tempLeft++; if (tempLeft < tempRight) array[tempRight] = array[tempLeft]; } array[tempLeft] = temp; QuickSort(array, left, tempLeft - 1); QuickSort(array, tempLeft + 1, right); }
三路划分(处理重复元素)
当数组中有大量重复值时,标准两路快速排序会频繁比对并交换。三路划分把数据分为 < pivot
, == pivot
, > pivot
三部分,递归左右两部分。
伪码思路(经典 Dijkstra):
lt = left; i = left+1; gt = right; v = a[left] while i <= gt: if a[i] < v: swap(a[lt], a[i]); lt++; i++ else if a[i] > v: swap(a[i], a[gt]); gt-- else: i++
工程化建议
对小区间(n <= 16 或 32)使用插入排序收尾
使用随机枢轴或三数取中来降低最坏情况概率
若数据重复键多,使用三路划分
对递归栈担心可改为手动栈(迭代)或在递归时先递归处理小区间以保证栈深 O(log n)
6. 归并排序(Merge Sort)
历史小记
John von Neumann 在 1945 年提出,将分治思想用于排序,并提出了合并有序序列的基本方法。
核心思想
把数组不断二分,直到子数组长度为 1,然后按两两合并有序子数组直至完成。合并操作在时间上是线性的。
两种常见实现
自顶向下(递归):最直观,返回新数组或使用辅助数组。调用示例要接收返回值(如
arr = MergeSort(arr)
)。自底向上(迭代):先合并长度为 1 的段,再合并长度为 2 的段,4、8、16……,避免递归开销。
public static int[] MergeSort(int[] array) { if (array.Length < 2) return array; int mid = array.Length / 2; int[] left = new int[mid]; int[] right = new int[array.Length - mid]; Array.Copy(array, 0, left, 0, mid); Array.Copy(array, mid, right, 0, array.Length - mid); return Merge(MergeSort(left), MergeSort(right)); } public static int[] Merge(int[] left, int[] right) { int[] result = new int[left.Length + right.Length]; int i = 0, a = 0, b = 0; while (a < left.Length && b < right.Length) { if (left[a] <= right[b]) result[i++] = left[a++]; else result[i++] = right[b++]; } while (a < left.Length) result[i++] = left[a++]; while (b < right.Length) result[i++] = right[b++]; return result; }
复杂度与性质
时间:始终 O(n log n)
空间:需要 O(n) 额外空间(数组版本);链表版本可做到 O(1) 附加空间
稳定:是稳定排序
工程建议
如果要排序外部大数据(磁盘/网络)或链表,归并是很好选择
自底向上实现可减少函数开销
若内存受限,考虑原地归并(实现复杂且效率不一定好)
7. 堆排序(Heap Sort)
历史小记
堆(binary heap)思想用于排序由 J. W. J. Williams 等在 1960s 次提出。堆排序把数组看作完全二叉树并进行堆化与下沉。
核心思想
把数组建成一个大顶堆(heapify)——线性时间 O(n)。
把堆顶(最大值)与末尾元素交换,堆长度减一,对堆顶做下沉(heapify)——O(log n);重复直到排序完成。
public static void HeapCompare(int[] array, int nowIndex, int arrayLength) { int left = 2 * nowIndex + 1; int right = 2 * nowIndex + 2; int biggerIndex = nowIndex; if (left < arrayLength && array[left] > array[biggerIndex]) biggerIndex = left; if (right < arrayLength && array[right] > array[biggerIndex]) biggerIndex = right; if (biggerIndex != nowIndex) { int temp = array[nowIndex]; array[nowIndex] = array[biggerIndex]; array[biggerIndex] = temp; HeapCompare(array, biggerIndex, arrayLength); } } public static void BuildBigHeap(int[] array) { for (int i = array.Length / 2 - 1; i >= 0; i--) HeapCompare(array, i, array.Length); } public static void HeapSort(int[] array) { BuildBigHeap(array); for (int i = array.Length - 1; i > 0; i--) { int temp = array[0]; array[0] = array[i]; array[i] = temp; HeapCompare(array, 0, i); // 注意传入当前堆大小 i } }
复杂度
时间:始终 O(n log n)
空间:O(1)(就地排序)
稳定性:不稳定
工程建议与坑
建堆阶段是线性的(O(n))而非 O(n log n)
递归
HeapCompare
可写成迭代下沉避免栈深堆排序访问模式跳跃(缓存局部性不好),在真实数据上通常比快排慢
8. 实战建议:何时选哪种排序 & 基准方法
何时选
内建 sort(Array.Sort / List.Sort):优先使用,语言库对各种场景做了工程化优化
需要稳定排序:用归并或库里的稳定实现
内存敏感并想原地:堆排序(但它不是最快)
大多数通用场景:快速排序(或库实现的 hybrid)
几乎有序或小数组:插入排序或 Shell
基准测试建议
使用固定随机种子、多次运行取平均
测试类型:随机、已排序、逆序、大量重复键、部分有序
使用
Stopwatch
测量并克隆数组避免原地破坏样本
示例基准(伪码):
int[] arr = GenerateRandom(n, seed); int[] a = (int[])arr.Clone(); Stopwatch sw = Stopwatch.StartNew(); QuickSort(a,0,a.Length-1); sw.Stop();
常见坑速查表
快排死循环:分区时
<=
/>=
使用不当或递归出口if (left >= right)
未写归并无效:自顶向下忘记接收返回数组
堆排序越界:heapify 使用
arrayLength
边界判断写错Shell 性能差:gap 序列选得不合适
9. 附:C# 基准测试模板与调试技巧
简易基准模板
public static void RunBenchmark(Action<int[]> sortFunc, int[] data, string name) { int[] copy = (int[])data.Clone(); var sw = System.Diagnostics.Stopwatch.StartNew(); sortFunc(copy); sw.Stop(); Console.WriteLine($"{name}: {sw.Elapsed.TotalMilliseconds} ms"); }
把每种算法包装为 Action<int[]>
调用,分别运行不同输入类型(随机/已序/逆序/重复等)。
调试技巧
打印中间状态(如对某个小数组逐步打印分区过程)帮助理解
单步调试分区/堆化函数,观察指针(tempLeft/tempRight)如何移动
对堆排序,用小数组手动画出堆索引关系验证
left/right
计算是否正确