五大排序算法完全详解(QuickSort / MergeSort / HeapSort / InsertionSort / ShellSort)

落小泪3周前技术实现101

五大排序算法完全详解(QuickSort / MergeSort / HeapSort / InsertionSort / ShellSort)


目录

  1. 由来与发展(Timeline)

  2. 总览比较表

  3. 插入排序(Insertion Sort)

  4. 希尔排序(Shell Sort)

  5. 快速排序(Quick Sort)

  6. 归并排序(Merge Sort)

  7. 堆排序(Heap Sort)

  8. 实战建议:何时选哪种排序 & 基准方法

  9. 附: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²)视 gapO(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,然后按两两合并有序子数组直至完成。合并操作在时间上是线性的。

两种常见实现

  1. 自顶向下(递归):最直观,返回新数组或使用辅助数组。调用示例要接收返回值(如 arr = MergeSort(arr))。

  2. 自底向上(迭代):先合并长度为 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 次提出。堆排序把数组看作完全二叉树并进行堆化与下沉。

核心思想

  1. 把数组建成一个大顶堆(heapify)——线性时间 O(n)。

  2. 把堆顶(最大值)与末尾元素交换,堆长度减一,对堆顶做下沉(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 计算是否正确


返回列表

上一篇:《FarmTutorial》类星露谷游戏

没有最新的文章了...

相关文章

A星算法的实现

A星算法的实现

1. A* 算法是什么?A* 算法是一种启发式搜索(Heuristic Search),它结合了 Dijkstra 的最短路径思想和 贪心搜索 的目标导向,既能保证路径的最优,又能提升搜索效率。其核心...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。