引言

排序算法（sorting algorithm）是用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。

如图 1-1 所示，排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符 ASCII 码顺序或自定义规则。

排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

关于时间复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 O 表示。

简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计。基于比较的排序算法的时间复杂度下限是 O(nlogn) 的。当然也有不是 O(nlogn) 的。例如，计数排序的时间复杂度是 O(n + w) ，其中 w 代表输入数据的值域大小。

1. 平方阶 O(n2) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
2. 线性对数阶 O(nlog2n) 排序 快速排序、堆排序和归并排序；
3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于空间复杂度

与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。一般来说，空间复杂度越小，算法越好。

关于稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 A 和 B，且在原本的列表中 A 出现在 B 之前，在排序过的列表中 A 也将会是在 B 之前。

• 稳定：如果 A 原本在 B 前面，而 𝐴=𝐵，排序之后 A 仍然在 B 的前面。
• 不稳定：如果 A 原本在 B 的前面，而 𝐴=𝐵，排序之后 A 可能会出现在 B 的后面。

👍 稳定的排序算法：冒泡排序、 插入排序、归并排序、计数排序和基数排序。

🖐️ 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释

n：数据规模

k：“桶”的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

理想排序算法

运行快、原地、稳定、正向自适应、通用性好。显然，迄今为止尚未发现兼具以上所有特性的排序算法。因此，在选择排序算法时，需要根据具体的数据特点和问题需求来决定。

接下来，我们将共同学习各种排序算法，并基于上述评价维度对各个排序算法的优缺点进行分析。

算法分类

十种常见排序算法可以分类两大类别：比较类排序和非比较类排序。

常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。

在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 log n 次，所以时间复杂度平均 O(nlogn)。

比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

而计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。

非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置（典型的空间换时间思想）。所以对数据规模和数据分布有一定的要求。

---

一：冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为最小的元素会经由交换慢慢“浮”到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

要点 💥

• 每轮冒泡不断地比较相邻的两个元素，如果它们是逆序的，则交换它们的位置
• 下一轮冒泡，可以调整未排序的右边界，减少不必要比较

2. 动图演示

3. 什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

4. 什么时候最慢

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

5. 代码实现🎆

public int[] bubbleSort(int[] nums) {
  // 未排序数据的右边界
  int j = nums.length - 1;
  do {
    //定义一个变量 x 记录未排序区域的右边界
    int x = 0;
    for (int i = 0; i < j; i++) {
      if (nums[i] > nums[i + 1]) { // 相邻元素中前面的元素大则交换
        int t = nums[i];
        nums[i] = nums[i + 1];
        nums[i + 1] = t;
        // 每次交换后，更新变量x,最后一次交换后x的值为经过一轮排序后新的右边界，优化代码
        x = i;
      }
    }
    j = x;
  } while (j != 0);
  return nums;
}

public void bubbleSort(int[] nums, int j) {
    if (j == 0) {
        return;
    }
    //定义一个变量 x 记录未排序区域的右边界
    int x = 0;
    for (int i = 0; i < j; i++) {
        if (nums[i] > nums[i + 1]) { // 相邻元素中前面的元素大则交换
            int t = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = t;
            // 每次交换以后，更新x <未排序数据的右边界> 的值
            x = i;
        }
    }
    bubbleSort(nums, x);
}

public static int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {// 相邻元素中前面的元素大则交换
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                // Change flag 只要一轮循环发生了交换，则把flag置为false
                flag = false;
            }
        }
        // 一轮都没有发生交换，没必要继续，直接退出循环
        if (flag) {
            break;
        }
    }
    return arr;
}

此处对代码做了一个小优化，加入了 is_sorted Flag，目的是将算法的最佳时间复杂度优化为 O(n)，即当原输入序列就是排序好的情况下，该算法的时间复杂度就是 O(n)。

6. 算法分析

• 稳定性：稳定
• 时间复杂度：最佳：𝑂(𝑛) ，最差：𝑂(𝑛2)， 平均：𝑂(𝑛2)
• 空间复杂度：𝑂(1)
• 排序方式：In-place

---

二：选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

1. 算法步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

要点 💥

• 每一轮选择，找出最大（最小）的元素，并把它交换到合适的位置

2. 动图演示

3. 代码实现🎆

public void selectSort(int[] nums) {
    // 1. 选择轮数：a.length - 1
    // 2. 交换的索引right初始化为a.length - 1，每次递减，将选择到的最大值与right位置交换
    for (int right = nums.length - 1; right > 0; right--) {
        int max = right;
        for (int i = 0; i < right; i++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }
        // max 值发生了变化才交换，否则不需要交换
        if (max != right) {
            // 每一轮循环结束时，将选择到的最大的的值交换到最右侧
            int t = nums[max];
            nums[max] = nums[right];
            nums[right] = t;
        }
    }
}

public void selectionSort(int[] arr) {
    // 每一轮循环结束时，将选择到的最小的的值交换到最左侧 同上
    for (int left = 0; left < arr.length - 1; left++) {
        int minIndex = left;
        for (int j = left + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != left) {
            int tmp = arr[left];
            arr[left] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
}

4. 算法分析

• 稳定性：不稳定

如图下图所示，元素 nums[ i ] 有可能被交换至与其相等的元素的右边，导致两者的相对顺序发生改变。

• 时间复杂度：最佳：𝑂(𝑛2) ，最差：𝑂(𝑛2)， 平均：𝑂(𝑛2)
• 空间复杂度：𝑂(1)
• 排序方式：In-place

---

三：插入排序 (Insertion Sort)

插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。

具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

下图展示了数组插入元素的操作流程。设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1. 算法步骤

插入排序的整体流程如图 11-7 所示。

1. 1. 初始状态下，数组的第 1 个元素已完成排序。
   2. 选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
   3. 选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
   4. 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。

要点：💥

• 将数组分为两部分[0 .. low-1] [low .. a.length-1]

• • 左边[0 .. low-1]是已排序部分
  • 右边[low .. a.length-1]是未排序部分

• 每次从未排序区域取出low位置的元素, 插入到已排序区域

2. 动图演示

3.代码实现🎆

public void insertionSort(int[] nums) {
    // 定义一个low指针，指向未排序区域的第一个数，默认从1开始，认为第一个数已经有序
    for (int notSortedFirstIndex = 1; notSortedFirstIndex < nums.length; notSortedFirstIndex++) {
        // 定义一个指针指向已排序区域的最后一个指针
        int sortedLastIndex = notSortedFirstIndex - 1;
        // 记录未排序区域的第一个值，用于后序插入
        int current = nums[notSortedFirstIndex];
        // 如果以排序区域的最后一个值大于未排序区域的第一个值，则将已排序区域的最后一个值向后移动
        while (sortedLastIndex >= 0 && nums[sortedLastIndex] > current) {
            nums[sortedLastIndex + 1] = nums[sortedLastIndex];
            sortedLastIndex--;
        }
        // 循环结束，说明已经找到插入位置
        if (sortedLastIndex != notSortedFirstIndex - 1) {
            // 上面的i是经过--以后不满足while条件退出循环，因此在插入时需要在i+1位置插入
            nums[sortedLastIndex + 1] = current;
        }
    }
}

/* 插入排序 */
void insertionSort(int[] nums) {
    // 外循环：已排序区间为 [0, i-1]
    for (int i = 1; i < nums.length; i++) {
        int base = nums[i], j = i - 1;
        // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        nums[j + 1] = base;        // 将 base 赋值到正确位置
    }
}

4. 算法分析

• 稳定性：稳定

在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序。

• 时间复杂度：最佳：𝑂(𝑛) ，最差：𝑂(𝑛2)， 平均：𝑂(𝑛2)
• 空间复杂度：O(1)
• 排序方式：In-place

5. 插入排序的优势

插入排序的时间复杂度为 𝑂(𝑛2) ，而我们即将学习的快速排序的时间复杂度为 𝑂(𝑛log⁡𝑛) 。尽管插入排序的时间复杂度更高，但在数据量较小的情况下，插入排序通常更快。

这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 𝑂(𝑛log⁡𝑛) 的算法属于基于分治策略的排序算法，往往包含更多单元计算操作。而在数据量较小时，𝑛2 和 𝑛log⁡𝑛 的数值比较接近，复杂度不占主导地位，每轮中的单元操作数量起到决定性作用。

实际上，许多编程语言（例如 Java）的内置排序函数采用了插入排序，大致思路为：对于长数组，采用基于分治策略的排序算法，例如快速排序；对于短数组，直接使用插入排序。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 𝑂(𝑛2) ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

• 冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
• 选择排序在任何情况下的时间复杂度都为 𝑂(𝑛2) 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。
• 选择排序不稳定，无法应用于多级排序。

---

四：希尔排序 (Shell Sort)

希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序的实质是分组插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 O(n2) 的第一批算法之一，但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是： 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长或增量)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

1.算法步骤

我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以gap=gap/2的方式，这种增量选择我们可以用一个序列来表示 {} ，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 { 𝑡1 , 𝑡2 , … , 𝑡𝑘 }，其中 𝑡𝑖 > 𝑡𝑗 , 𝑖 < 𝑗 , 𝑡𝑘 = 1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

要点:💥

• 简单的说，就是分组实现插入，每组元素间隙称为 gap
• 每轮排序后 gap 逐渐变小，直至 gap 为 1 完成排序
• 对插入排序的优化，让元素更快速地交换到最终位置

下图演示了 gap = 4，gap = 2，gap = 1 的三轮排序前后比较

2.图解算法

3.模拟算法

下面以数列{80,30,60,40,20,10,50,70}为例，演示它的希尔排序过程。

第1趟: (gap=4)

当gap=4时,意味着将数列分为4个组: {80,20},{30,10},{60,50},{40,70}。 对应数列: {80,30,60,40,20,10,50,70} 对这4个组分别进行排序，排序结果: {20,80},{10,30},{50,60},{40,70}。 对应数列: {20,10,50,40,80,30,60,70}

第2趟: (gap=2)

当gap=2时,意味着将数列分为2个组: {20,50,80,60}, {10,40,30,70}。 对应数列: {20,10,50,40,80,30,60,70} 注意: {20,50,80,60}实际上有两个有序的数列{20,80}和{50,60}组成。 {10,40,30,70}实际上有两个有序的数列{10,30}和{40,70}组成。 对这2个组分别进行排序，排序结果: {20,50,60,80}, {10,30,40,70}。 对应数列: {20,10,50,30,60,40,80,70}

第3趟: (gap=1)

当gap=1时,意味着将数列分为1个组: {20,10,50,30,60,40,80,70} 注意: {20,10,50,30,60,40,80,70}实际上有两个有序的数列{20,50,60,80}和{10,30,40,70}组成。

Tips

通过上述的代码模拟过程，我们可以看到，希尔排序每轮将以 gap 为间隙的数据分为一组，对分好的组内先进行一轮插入排序，然后使得 gap 缩小，意味着每一组中的数据个数变多，但是，这一组数据是在前一轮排序后重新分组的，也就是说第二轮排序是在第一轮排序的基础之上，那么组内元素就有第一轮排序的前提，也就是局部有序的，这充分了利用了插入排序对于局部有序数据排序的高效性。后序轮次以此类推，直到 gap 缩小为 1，也就是只分一组，对所有元素进行最后一轮排序。

4.代码实现🎆

public void shellSort(int[] nums) {
    // 定义分组间隙 gap ，初始为数组长度的一半，每次循环右位移一位（除以二）
    for (int gap = nums.length >> 1; gap >= 1; gap = gap >> 1) {
        // notSortedFirstIndex 未排序数组的第一个指针
        for (int notSortedFirstIndex = gap; notSortedFirstIndex < nums.length; notSortedFirstIndex++) {
            // 未排序区域的第一个元素值
            int current = nums[notSortedFirstIndex];
            int sortedLastIndex = notSortedFirstIndex - gap; // 排序数组的最后一个数据指针
            // 插入排序的过程
            while (sortedLastIndex >= 0 && nums[sortedLastIndex] > current) {
                nums[sortedLastIndex + gap] = nums[sortedLastIndex];
                sortedLastIndex -= gap;
            }
            if (sortedLastIndex != notSortedFirstIndex - gap) {
                nums[sortedLastIndex + gap] = current;
            }
        }
    }
}

public void shellSort(int[] arr) {
    int gap = arr.length >> 1;
    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            // 未排序区域的第一个元素值
            int current = arr[i];
            // 已排序区域的最后一个元素指针
            int preIndex = i - gap;
            // Insertion sort
            while (preIndex >= 0 && arr[preIndex] > current) {
                // 后移
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = current;

        }
        // 取下一个希尔增量
        gap = gap >> 1;
    }
}

5.算法分析

• 稳定性：不稳定
• 时间复杂度：最佳：𝑂(𝑛𝑙𝑜𝑔𝑛)， 最差：𝑂(𝑛2) 平均：𝑂(𝑛𝑙𝑜𝑔𝑛)
• 空间复杂度：O(1)

---

五：归并排序(merge sort)

归并排序（merge sort）是一种基于分治策略的排序算法，包含下图所示的“划分”和“合并”阶段。

1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 𝑂(𝑛𝑙𝑜𝑔𝑛) 的时间复杂度。代价是需要额外的内存空间。（空间换时间思想）

根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。

所谓 自下至上 就是先排序2个元素，再归并为4个元素排序，再归并为8个元素排序

而 自上至下 就是先排序 数组长度一半的元素，再拆分为四分之一，八分之一

1.算法步骤

从下往上的归并排序

将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。(参考下面的图片)

从上往下的归并排序

它与"从下往上"在排序上是反方向的。它基本包括3步:

• 分 - 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
• 治 - 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。（后序可以结合插入排序进行优化）
• 合 - 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

要点:💥

• 分 - 每次从中间切一刀，处理的数据少一半
• 治 - 当数据仅剩一个时可以认为有序
• 合 - 两个有序的结果，可以进行合并排序

2.动图演示

以下动图演示的是从下往上的归并排序

3.模拟算法

从上往下的归并排序

从上往下的归并排序采用了递归的方式实现。它的原理非常简单，如下图:

通过"从上往下的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时:

• 将数组{80,30,60,40,20,10,50,70}看作由两个有序的子数组{80,30,60,40}和{20,10,50,70}组成。对两个有序子树组进行排序即可。

• • 将子数组{80,30,60,40}看作由两个有序的子数组{80,30}和{60,40}组成。
  • 将子数组{20,10,50,70}看作由两个有序的子数组{20,10}和{50,70}组成。

• 将子数组{80,30}看作由两个有序的子数组{80}和{30}组成。
• 将子数组{60,40}看作由两个有序的子数组{60}和{40}组成。
• 将子数组{20,10}看作由两个有序的子数组{20}和{10}组成。
• 将子数组{50,70}看作由两个有序的子数组{50}和{70}组成。

从下往上的归并排序

从下往上的归并排序的思想正好与"从下往上的归并排序"相反。如下图:

通过"从下往上的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时:

• 将数组{80,30,60,40,20,10,50,70}看作由8个有序的子数组{80},{30},{60},{40},{20},{10},{50}和{70}组成。
• 将这8个有序的子数列两两合并。得到4个有序的子树列{30,80},{40,60},{10,20}和{50,70}。
• 将这4个有序的子数列两两合并。得到2个有序的子树列{30,40,60,80}和{10,20,50,70}。
• 将这2个有序的子数列两两合并。得到1个有序的子树列{10,20,30,40,50,60,70,80}。

4.代码实现🎆

public void mergeSort(int[] nums) {
    int[] arr = new int[nums.length];
        /*
         * 参数一：待排序数组
         * 参数二：待排序数组的区域左标
         * 参数二：待排序数组的区域右标
         * 参数三：临时数组，用来合并数组时使用
         */
    split(nums, 0, nums.length - 1, arr);
}

    private void split(int[] nums, int left, int right, int[] arr) {
    // 治
    if (left == right) {
        return;
    }
    // 分
    int mid = (left + right) >>> 1;
    split(nums, left, mid, arr);
    split(nums, mid + 1, right, arr);
    // 合
    merge(nums, left, mid, mid + 1, right, arr);
    System.arraycopy(arr, left, nums, left, right - left + 1);
}

    /**
     * 合并有序数组
     *
     * @param nums 原始数组
     * @param i  iEnd 第一个有序范围
     * @param j  jEnd 第二个有序范围
     * @param arr 临时数组
     */
private void merge(int[] nums, int i, int iEnd, int j, int jEnd, int[] arr) {
    // 定义一个指针k用于构建临时数组
    int k = i;
    while (i <= iEnd && j <= jEnd) {
        // 每次将 i ~ iEnd 或者 j ~ jEnd 中更小的数加入到临时数组，并将指针后移
        if (nums[i] < nums[j]) {
            arr[k] = nums[i];
            i++;
        } else {
            arr[k] = nums[j];
            j++;
        }
        k++;
    }
    // 当 i ~ iEnd 或 j ~ jEnd 其中一个区域的数据全部被加入到临时数组，则把另一个区域的数据拷贝到临时数组中
    if (i > iEnd) {
        System.arraycopy(nums, j, arr, k, jEnd - j + 1);
    }
    if (j > jEnd) {
        System.arraycopy(nums, i, arr, k, iEnd - i + 1);
    }
}

public void mergeSort(int[] nums) {
    int len = nums.length;
    int[] arr = new int[len];
    // width 代表有序区间的宽度，取值依次为 1,2,4 ...
    for (int width = 1; width < len; width *= 2) {
        // [left,right] 分别代表合并区间的左右边界
        // 每次合并两个有序区间，因此左边界每次循环 ＋ 2 * width
        for (int left = 0; left < len; left += 2 * width) {
            //右边界为下次左边界 - 1
            int right = Math.min(len - 1, left + 2 * width - 1);
            //中间值mid为左边界 + 一个宽度width - 1
            int mid = Math.min(len - 1, left + width - 1);
            merge(nums, left, mid, mid + 1, right, arr);
        }
        System.arraycopy(arr, 0, nums, 0, len);
    }
}
    /**
     * 合并有序数组
     *
     * @param nums 原始数组
     * @param i  iEnd 第一个有序范围
     * @param j  jEnd 第二个有序范围
     * @param arr 临时数组
     */
private void merge(int[] nums, int i, int iEnd, int j, int jEnd, int[] arr) {
    // 定义一个k操作临时数组
    int k = i;
    //如果i和j都在有效范围内
    while (i <= iEnd && j <= jEnd) {
        //比较i和j处索引的数组的值，并把较小的值加入到临时数组a2中
        if (nums[i] < nums[j]) {
            arr[k] = nums[i];
            i++;
        } else {
            arr[k] = nums[j];
            j++;
        }
        //更新操作临时数组的指针
        k++;
    }
    // 当i > iEnd说明第一个有序范围内的元素已经全部迭代，将第二范围内没有被迭代的元素拷贝到arr数组即可
    if (i > iEnd) {
        System.arraycopy(nums, j, arr, k, jEnd - j + 1);
    }
    // 当j > jEnd说明第二个有序范围内的元素已经全部迭代，将第一范围内没有被迭代的元素拷贝到arr数组即可
    if (j > jEnd) {
        System.arraycopy(nums, i, arr, k, iEnd - i + 1);
    }
}

代码优化：

通过上面学习的两类排序算法插入排序和归并排序，我们发现，如果是小数据量且有序度高时，插入排序的效果要高于归并排序，而如果数据量很大时，更适合使用归并排序，因此，我们可以结合两类排序的优缺点，于是有了下述 归并排序+插入排序：

当分区范围 <= 32 后，采用插入排序实现有序！

传统的归并排序必须等到 left == right 即分区范围内只有一个元素时才视为有序，通过整合插入排序，可以对小范围内（<=32）的元素直接采用插入排序后即可视为有序，不用一直递归调用直到分区内只有一个元素，提高效率和性能。

public static void mergeInsertionSort(int[] a) {
    int[] a2 = new int[a.length];
    split(a, 0, a.length - 1, a2);
}

//归并排序分区方法
private static void split(int[] a, int left, int right, int[] a2) {
    // 治：当分区范围 <= 32后，采用插入排序实现有序
    // 传统的归并排序必须等到 left == right 即分区范围内只有一个元素时才视为有序
    // 通过整合插入排序，可以对小范围内（<=32）的元素直接采用插入排序后即可视为有序
    // 不用一直递归调用到分区内只有一个元素，提高效率和性能
    if (right - left <= 32) {
        //插入排序
        insertionSort(a, left, right);
        return;
    }
    // 分
    int mid = (right - left) >>> 1;
    split(a, left, mid, a2);
    split(a, mid + 1, right, a2);
    // 合
    merge(a, left, mid, mid + 1, right, a2);
    System.arraycopy(a2, left, a, left, right - left + 1);
}

/**
     * 插入排序
     */
private static void insertionSort(int[] a, int left, int right) {
    for (int low = left + 1; low <= right; low++) {
        //定义一个变量t记录未排序区域的第一个值
        int t = a[low];
        //定义一个指针 i 为已排序区域的最后一个值的指针
        int i = low - 1;
        while (i >= left && a[i] > t) {
            a[i + 1] = a[i];
            i--;
        }
        //循环结束，说明找到了插入位置，插入即可
        if (i != low - 1) {
            a[i + 1] = t;
        }
    }
}

/**
     * 合并有序数组
     *
     * @param a1 原始数组
     * @param i  iEnd 第一个有序范围
     * @param j  jEnd 第二个有序范围
     * @param a2 临时数组
     */
private static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
    //定义变量k为操作临时数组的指针
    int k = i;
    //如果i和j都在有效范围内
    while (i <= iEnd && j <= jEnd) {
        //比较i和j处索引的数组的值，并把较小的值加入到临时数组a2中
        if (a1[i] < a1[j]) {
            a2[k] = a1[i];
            i++;
        } else {
            a2[k] = a1[j];
            j++;
        }
        //更新操作临时数组的指针
        k++;
    }
    // 当i > iEnd说明第一个有序范围内的元素已经全部迭代，将第二范围内没有被迭代的元素拷贝到a1数组即可
    if (i > iEnd) {
        System.arraycopy(a1, j, a2, k, jEnd - j + 1);
    }
    // 当j > jEnd说明第二个有序范围内的元素已经全部迭代，将第一范围内没有被迭代的元素拷贝到a1数组即可
    if (j > jEnd) {
        System.arraycopy(a1, i, a2, k, iEnd - i + 1);
    }
}

5.算法分析

• 稳定性：稳定
• 时间复杂度：最佳：𝑂(𝑛𝑙𝑜𝑔𝑛)， 最差：𝑂(𝑛𝑙𝑜𝑔𝑛)， 平均：𝑂(𝑛𝑙𝑜𝑔𝑛)
• 空间复杂度：O(n)

六：快速排序(quick sort)

快速排序（quick sort）又称分区交换排序，是一种基于分治策略的排序算法，简称「快排」，运行高效，应用广泛。快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。

快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如图下图所示。（图示只是快速排序算法中其中一种分区方法，具体的其他分区方法将在下面介绍）

1. 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
2. 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
3. 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。

快速排序的分治策略：

哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。

1.算法步骤

快速排序的整体流程如下图所示。

1. 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
2. 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
3. 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

2.动图演示

3.快速排序为什么快

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。

• 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 𝑂(𝑛2) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 𝑂(𝑛log⁡𝑛) 的时间复杂度下运行。
• 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
• 复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

4.算法优化

基准数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 𝑛−1、右子数组长度为 0 。如此递归下去，每轮哨兵划分后都有一个子数组的长度为 0 ，分治策略失效，快速排序退化为“冒泡排序”的近似形式。

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至 𝑂(𝑛2) 的概率大大降低。示例代码如下：

/* 选取三个候选元素的中位数 */
int medianThree(int[] nums, int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m 在 l 和 r 之间
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l 在 m 和 r 之间
    return right;
}

/* 哨兵划分（三数取中值） */
int partition(int[] nums, int left, int right) {
    // 选取三个候选元素的中位数
    int med = medianThree(nums, left, (left + right) / 2, right);
    // 将中位数交换至数组最左端
    swap(nums, left, med);
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
        j--;          // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
        i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left);  // 将基准数交换至两子数组的分界线
    return i;             // 返回基准数的索引
}

尾递归优化

在某些输入下，快速排序可能占用空间较多。以完全有序的输入数组为例，设递归中的子数组长度为 𝑚 ，每轮哨兵划分操作都将产生长度为 0 的左子数组和长度为 𝑚−1 的右子数组，这意味着每一层递归调用减少的问题规模非常小（只减少一个元素），递归树的高度会达到 𝑛−1 ，此时需要占用 𝑂(𝑛) 大小的栈帧空间。

为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 𝑛/2 ，因此这种方法能确保递归深度不超过 log⁡𝑛 ，从而将最差空间复杂度优化至 𝑂(log⁡𝑛) 。代码如下所示：

void quickSort(int[] nums, int left, int right) {
    // 子数组长度为 1 时终止
    while (left < right) {
        // 哨兵划分操作
        int pivot = partition(nums, left, right);
        // 对两个子数组中较短的那个执行快速排序
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // 递归排序左子数组
            left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // 递归排序右子数组
            right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

5.代码实现

单边循环快排

单边循环（lomuto分区）要点💥

• 选择最右侧元素作为基准点
• j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换

• • 交换时机：j 找到小的，且与 i 不相等
  • i 找到 >= 基准点元素后，不应自增

• 最后基准点与 i 交换，i 即为基准点最终索引

例：

i 和 j 都从左边出发向右查找，i 找到比基准点4大的5，j找到比基准点小的2，停下来交换

i 找到了比基准点大的5，j 找到比基准点小的3，停下来交换

j 到达right 处结束，right 与 i 交换，一轮分区结束

public void quickSort(int[] nums) {
    doQuickSort(nums, 0, nums.length - 1);
}

private void doQuickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    // 分区
    int p = partition(nums, left, right);
    doQuickSort(nums, left, p - 1);
    doQuickSort(nums, p + 1, right);
}

/**
     * 单边循环快排（lomuto 洛穆托分区方案）
     * 核心思想：每轮找到一个基准点元素，把比它小的放到它左边，比它大的放到它右边，这称为分区
     * 
     * 	1.选择最右元素作为基准点元素
     * 	2.j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
     * 		· 交换时机：j 找到小的，且与 i 不相等
     * 		· i 找到 >= 基准点元素后，不应自增 
     * 	3.最后基准点与 i 交换，i 即为基准点最终索引
     * 
     */
private int partition(int[] nums, int left, int right) {
    int pv = nums[right]; // 基准元素
    int i = left; // 找比基准点大的值，如果找到大于等于基准点的值，不在移动
    int j = left; // 找比基准点小的值
    while (j < right) {
        if (nums[j] < pv) {
            if (j != i) {
                swap(nums, i, j);
            }
            // 只有找到的值比基准点小,i才++，如果大于基准点的值,i不变,j++
            // 等到下次找到比基准点小的值,i和j不相等，进行交换
            i++;
        }
        j++;
    }
    swap(nums, right, i);
    return i;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

双边循环快排

双边循环要点💥

• 选择最左侧元素作为基准点
• j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换

• • i 从左向右
  • j 从右向左

• 最后基准点与 i 交换，i 即为基准点最终索引

例：

i 找到比基准点大的5停下来，j 找到比基准点小的1停下来（包含等于），二者交换

i 找到8，j 找到3，二者交换，i 找到7，j 找到2，二者交换

i == j，退出循环，基准点与 i 交换

public void quickSort(int[] nums) {
    doQuickSort(nums, 0, nums.length - 1);
}

private void doQuickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int p = partition(nums, left, right);
    doQuickSort(nums, left, p - 1);
    doQuickSort(nums, p + 1, right);
}

/**
     * 双边循环快排
     * 1.选择最左元素作为基准点元素 
     * 2.j 指针负责从右向左找比基准点小或等的元素，i 指针负责从左向右找比基准点大的元素，
                                                     一旦找到二者交换，直至 i，j 相交
     * 3.最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置
     */
private int partition(int[] nums, int left, int right) {
    /***************************随机元素作为基准点***************************/
    int index = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
    swap(nums,index,left);
    /***************************随机元素作为基准点***************************/
    int pv = nums[left]; // 选择最左侧元素作为基准点
    int i = left; // i 指针从左到右找大于基准点的值
    int j = right; // j 指针从右到左找小于基准点的值
    while (i < j) {
        // 必须先处理j指针再处理i指针
        // 1. j 从右向左找小(等)的
        while (i < j && nums[j] > pv) {
            j--;
        }
        // 2. i 从左向右找大的
        while (i < j && nums[i] <= pv) {
            i++;
        }
        // 3. 交换位置
        swap(nums, i, j);
    }
    swap(nums, left, j);
    return j;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

随机基准点+处理重复值 双边循环快速排序

随机基准点或者使用三个候选元素：

使用随机数作为基准点，避免万一最大值或最小值作为基准点导致的分区不均衡

使用多个候选元素取中位数的方式，基准数“既不太小也不太大”的概率将大幅提升。

例如：

处理重复值：

如果重复值较多，则原来算法中的分区效果也不好，如下图中左侧所示，需要想办法改为右侧的分区效果

• 核心思想是

• • 改进前，i 只找大于的，j 会找小于等于的。一个不找等于、一个找等于，势必导致等于的值分布不平衡
  • 改进后，二者都会找等于的交换，等于的值会平衡分布在基准点两边

• 细节：

• • 因为一开始 i 就可能等于 j，因此外层循环需要加等于条件保证至少进入一次，让 j 能减到正确位置
  • 内层 while 循环中 i <= j 的 = 也不能去掉，因为 i == j 时也要做一次与基准点的判断，好让 i 及 j 正确
  • i == j 时，也要做一次 i++ 和 j-- 使下次循环二者不等才能退出
  • 因为最后退出循环时 i 会大于 j，因此最终与基准点交换的是 j 💥💥💥

• 内层两个 while 循环的先后顺序不再重要

public void quickSort(int[] nums) {
    doQuickSort(nums, 0, nums.length - 1);
}

private void doQuickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int p = partition(nums, left, right);
    doQuickSort(nums, left, p - 1);
    doQuickSort(nums, p + 1, right);
}


/*
核心思想是
* 改进前，i 只找大于的，j 会找小于等于的。一个不找等于、一个找等于，势必导致等于的值分布不平衡
* 改进后，二者都会找等于的交换，等于的值会平衡分布在基准点两边
     */
private int partition(int[] nums, int left, int right) {
    // 随机基准点
    int random = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
    swap(nums, left, random);
    // 基准点
    int pv = nums[left];
    int i = left + 1; // 在处理重复值时,i要从left + 1开始
    int j = right;
    while (i <= j) {
        // i 指针和 j 指针的先后处理方式不再重要
        // 处理重复值，i需要从左到右找大于等于基准点的值
        while (i <= j && nums[i] < pv) {
            i++;
        }
        // 处理重复值，j需要从右向左找小于等于基准点的值
        while (i <= j && nums[j] > pv) {
            j--;
        }
        if (i <= j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    swap(nums, j, left);
    return j;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

6.算法分析

• 稳定性：不稳定
• 时间复杂度：最佳：𝑂(𝑛𝑙𝑜𝑔𝑛)， 最差：𝑂(n2)，平均：𝑂(𝑛𝑙𝑜𝑔𝑛)
• 空间复杂度：𝑂(𝑛𝑙𝑜𝑔𝑛)

/

七：堆排序(Heap Sort)

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。

1. 输入数组并建立小顶堆，此时最小元素位于堆顶。
2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间。在实际中，我们通常使用一种更加优雅的实现方式。

堆排序在一定程度上有着与选择排序类似的思想，也是每次在数组中选择最大的元素的值然后交换到数组的最后一位，最终实现有序，但是传统的选择排序在选择最大值的过程中采用的是遍历比较，每次选择最大值都需要遍历未排序区域，但是，想要选择最大值，堆数据结构是一个非常合适的解决方法，我们将数据构建为堆数据结构，每次选择最大值只需要拿到堆顶元素即可，然后对堆做一次下潜操作，继续构建堆结构。

1.算法步骤

设数组的长度为 𝑛 ，堆排序的流程如下图所示。

1. 输入数组并建立大顶堆。完成后，最大元素位于堆顶。
2. 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 1 ，已排序元素数量加 1 。
3. 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复。
4. 循环执行第 2. 步和第 3. 步。循环 𝑛−1 轮后，即可完成数组排序。

在代码实现中，使用了与“堆”相同的从顶至底堆化 sift_down() 函数。值得注意的是，由于堆的长度会随着提取最大元素而减小，因此我们需要给 sift_down() 函数添加一个长度参数 𝑛 ，用于指定堆的当前有效长度。代码如下所示：

2.动图演示

3.代码实现

public static void heapSort(int[] a) {
    //建立大顶堆
    heapify(a, a.length);
    for (int right = a.length - 1; right > 0; right--) {
        swap(a, 0, right); //交换堆顶元素到未排序区域的最后一位（将最大值移动到最后）
        down(a, 0, right); //对于堆顶元素进行下潜操作，使其重新符合大顶堆特性
    }
}


    /**
     * 建推
     */
private static void heapify(int[] array, int size) {
    /*
        1.找到完全二叉树的最后一个非叶子节点     公式： size / 2 - 1
        2.从后向前，依次对每个非叶子节点调用下潜down方法
    */
    for (int i = (size >> 1) - 1; i >= 0; i--) {
        down(array, i, size);
    }
}

    /**
     * 下潜 <非递归实现>
     */
private static void down(int[] array, int parent, int size) {
    /*
    1.找到当前节点的左孩子节点和右孩子节点
    2.将当前节点的值和左孩子，右孩子的值进行比较
    3.定义一个变量max，用于存放当前节点与其左右孩子中最大的值的下标
    4.默认最大值先为当前节点，如果左孩子的值大于当前节点，更新max指针为左孩子下标，右孩子类似
    5.经过比较，如果max指针任然为父节点，说明没有发生交换，已经符合大顶堆特性，退出循环即可
    6.如果max不为父节点，交换当前父节点与max指针指向的节点的值，将max赋值给父节点，循环继续判断是否仍需要下潜
         */
    while (true) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int max = parent;
        if (left < size && array[left] > array[max]) {
            max = left;
        }
        if (right < size && array[right] > array[max]) {
            max = right;
        }
        // 没有发生交换
        if (max == parent) {
            break;
        }
        swap(array, max, parent);
        parent = max;
    }
}

    /**
     * 交换
     */
private static void swap(int[] array, int i, int j) {
    int t = array[i];
    array[i] = array[j];
    array[j] = t;
}

4.算法分析

• 稳定性：不稳定
• 时间复杂度：最佳：𝑂(𝑛𝑙𝑜𝑔𝑛)， 最差：𝑂(𝑛𝑙𝑜𝑔𝑛)， 平均：𝑂(𝑛𝑙𝑜𝑔𝑛)
• 空间复杂度：O(1)

八：计数排序 (Counting Sort)

计数排序（counting sort）通过统计元素数量来实现排序，通常应用于整数数组。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序 (Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。

1.算法步骤

先来看一个简单的例子。给定一个长度为 𝑛 的数组 nums ，其中的元素都是“非负整数”，计数排序的整体流程如下图所示。

1. 遍历数组，找出其中的最大数字，记为 𝑚 ，然后创建一个长度为 𝑚+1 的辅助数组 counter 。
2. 借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 1 即可。
3. 由于 counter 的各个索引天然有序，因此相当于所有数字已经排序好了。接下来，我们遍历 counter ，根据各数字出现次数从小到大的顺序填入 nums 即可。

(不可处理负数)要点：💥

1. 找到最大值，创建一个大小为 最大值+1 的 count 数组

2. count 数组的索引对应原始数组的元素，用来统计该元素的出现次数

3. 遍历 count 数组，根据 count 数组的索引（即原始数组的元素）以及出现次数，生成排序后内容

count 数组的索引是：已排序好的

前提：待排序元素 >=0 且最大值不能太大

(可处理负数)要点：💥

1. 让原始数组的最小值映射到 count[0] 最大值映射到 count 最右侧

2. 原始数组元素 - 最小值 = count 索引

3. count 索引 + 最小值 = 原始数组元素

2.动画演示

3.代码实现

public static void countingSort(int[] a) {
    // 1.获取数组最大值
    int max = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    // 2.创建一个长度为数组最大值 + 1的新数组
    int[] count = new int[max + 1];
    // 3.遍历原始数组，将对应数据索引处的值++（统计该元素的出现次数）
    for (int v : a) {
        count[v]++;
    }
    //定义一个指针k操作原始数组
    int k = 0;
    // 4.遍历count数组，将值大于0处的索引值添加到原始数组中
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            a[k++] = i;
            // 5.添加完成后，对应索引处的值--（表示出现次数-1）
            count[i]--;
        }
    }
}

public static void countSort(int[] a) {
    // 1.遍历数组，拿到数组中的最大值和最小值
    int max = a[0];
    int min = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] > max) {
            max = a[i];
        }
        if (a[i] < min) {
            min = a[i];
        }
    }
    // 2.实例化一个数组长度为 max - min + 1 的新数组
    int[] count = new int[max - min + 1];
    // 3.遍历原始数组，将原始数组中的(值 - min)与count数组索引做映射
    // 可以通过值 - min的方式将所有数据全部映射为大于零的数
    for (int v : a) {
        count[v - min]++; // v 原始数组元素 - 最小值 = count 索引
    }
    int k = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            // i + min 代表原始数组元素 count[i] 代表元素出现次数
            a[k++] = i + min;
            count[i]--;
        }
    }
}

4.完整实现

细心的读者可能发现了，如果输入数据是对象，上述步骤 3. 就失效了。假设输入数据是商品对象，我们想按照商品价格（类的成员变量）对商品进行排序，而上述算法只能给出价格的排序结果。

那么如何才能得到原数据的排序结果呢？我们首先计算 count 的“前缀和”。顾名思义，索引 i 处的前缀和 prefix[i] 等于数组前 i 个元素之和：

前缀和具有明确的意义，prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。这个信息非常关键，因为它告诉我们各个元素应该出现在结果数组的哪个位置。接下来，我们倒序遍历原数组 nums 的每个元素 num ，在每轮迭代中执行以下两步。

1. 将 num 填入数组 res 的索引 prefix[num] - 1 处。
2. 令前缀和 prefix[num] 减小 1 ，从而得到下次放置 num 的索引。

遍历完成后，数组 res 中就是排序好的结果，最后使用 res 覆盖原数组 nums 即可。下图展示了完整的计数排序流程。

public static void countSort(int[] nums) {
    // 1. 统计数组最大元素 max
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        max = Math.max(nums[i], max);
    }
    // 2. 统计各数字的出现次数
    int[] count = new int[max + 1];
    for (int num : nums) {
        count[num]++;
    }
    // 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
    int[] prefix = new int[count.length];
    prefix[0] = count[0];
    for (int i = 1; i < prefix.length; i++) {
        prefix[i] = count[i] + prefix[i - 1];
    }
    // 4. 倒序遍历 nums ，将各元素填入结果数组 res
    int[] res = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        int num = nums[i];
        res[prefix[num] - 1] = num;
        prefix[num]--;
    }
    // 使用结果数组 res 覆盖原数组 nums
    System.arraycopy(res, 0, nums, 0, nums.length);
}

5.算法分析

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量额外内存空间。

• 稳定性：稳定
• 时间复杂度：最佳：O(n+k) 最差：O(n+k) 平均：O(n+k)
• 空间复杂度：O(k)

九：桶排序(Bucket Sort)

桶排序（bucket sort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行）

1.算法步骤

考虑一个长度为 𝑛 的数组，其元素是范围 [0,1) 内的浮点数。桶排序的流程如下图所示。

1. 初始化 𝑘 个桶，将 𝑛 个元素分配到 𝑘 个桶中。
2. 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。
3. 按照桶从小到大的顺序合并结果。

2.动画演示

3.代码实现

    /**
     * 桶排序
     * @param nums 待排序数组
     * @param range 每个桶中数据的最大范围
     */
public static void bucketSort(int[] nums, int range) {
    // 1. 先求最大值和最小值（高效确定桶的个数）
    int max = nums[0];
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[i]);
    }
    // 2. 初始化桶的个数   桶的数量为(max-min)/range + 1
    int bucket_count = (max - min) / range + 1;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucket_count; i++) {
        buckets.add(new ArrayList<>());
    }
    // 遍历输入的数据 放入对应的桶中
    for (int num : nums) {
        // 计算当前元素应该存在在那个桶中
        int idx = (num - min) / range;
        buckets.get(idx).add(num);
    }
    int k = 0;
    for (List<Integer> bucket : buckets) {
        int[] array = bucket.stream().mapToInt(Integer::intValue).toArray();
        // 3.排序桶内元素
        Arrays.sort(array);
        for (int a : array) {
            nums[k++] = a;
        }
    }
}

4.如何实现平均分配

桶排序的时间复杂度理论上可以达到 𝑂(𝑛) ，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。例如，我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中，但商品价格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若将价格区间平均划分为 10 个，各个桶中的商品数量差距会非常大。

为实现平均分配，我们可以先设定一条大致的分界线，将数据粗略地分到 3 个桶中。分配完毕后，再将商品较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。

如图所示，这种方法本质上是创建一棵递归树，目标是让叶节点的值尽可能平均。当然，不一定要每轮将数据划分为 3 个桶，具体划分方式可根据数据特点灵活选择。

如果我们提前知道商品价格的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。

如下图所示，我们假设商品价格服从正态分布，这样就可以合理地设定价格区间，从而将商品平均分配到各个桶中。

5.算法分析

• 稳定性：稳定
• 时间复杂度：最佳：𝑂(𝑛+𝑘) 最差：𝑂(𝑛2) 平均：𝑂(𝑛+𝑘)
• 空间复杂度：𝑂(𝑛+𝑘)

十：基数排序（radix sort）

基数排序（radix sort）的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为 O(n×k)，n 为数组长度，k 为数组中元素的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

在上面我们介绍了计数排序，它适用于数据量 𝑛 较大但数据范围 𝑚 较小的情况。假设我们需要对 𝑛=106 个学号进行排序，而学号是一个 8 位数字，这意味着数据范围 𝑚=108 非常大，使用计数排序需要分配大量内存空间，而基数排序可以避免这种情况。

1.算法步骤

以学号数据为例，假设数字的最低位是第 1 位，最高位是第 8 位，基数排序的流程如图所示。

1. 初始化位数 𝑘=1 。
2. 对学号的第 𝑘 位执行“计数排序”。完成后，数据会根据第 𝑘 位从小到大排序。
3. 将 𝑘 增加 1 ，然后返回步骤 2. 继续迭代，直到所有位都排序完成后结束。

下面剖析代码实现。对于一个 𝑑 进制的数字 𝑥 ，要获取其第 𝑘 位 𝑥𝑘 ，可以使用以下计算公式：                ​​​​​​​        

其中 ⌊𝑎⌋ 表示对浮点数 𝑎 向下取整，而 mod𝑑 表示对 𝑑 取模（取余）。对于学号数据，𝑑=10 且 𝑘∈[1,8]

2.动画演示

3.代码实现

public static void radixSort(String[] a, int length) {
    // 1.准备桶
    ArrayList<String>[] buckets = new ArrayList[128];
    // 2.初始化桶
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<>();
    }
    // 3.从低位开始多轮桶排序
    for (int i = length - 1; i >= 0; i--) {
        // 4.将字符串放入合适的桶
        for (String v : a) {
            buckets[v.charAt(i)].add(v);
        }
        // 5.重新取出排好序的字符串，放回原始数组
        int k = 0;
        for (ArrayList<String> bucket : buckets) {
            for (String s : bucket) {
                a[k++] = s;
            }
            bucket.clear();
        }
    }
}

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
int digit(int num, int exp) {
    // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num / exp) % 10;
}

/* 计数排序（根据 nums 第 k 位排序） */
void countingSortDigit(int[] nums, int exp) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
    int[] counter = new int[10];
    int n = nums.length;
    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
        counter[d]++;                // 统计数字 d 的出现次数
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }
    // 倒序遍历，根据桶内统计结果，将各元素填入 res
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1; // 获取 d 在数组中的索引 j
        res[j] = nums[i];       // 将当前元素填入索引 j
        counter[d]--;           // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for (int i = 0; i < n; i++)
    nums[i] = res[i];
}

/* 基数排序 */
void radixSort(int[] nums) {
    // 获取数组的最大元素，用于判断最大位数
    int m = Integer.MIN_VALUE;
    for (int num : nums)
    if (num > m)
        m = num;
    // 按照从低位到高位的顺序遍历
    for (int exp = 1; exp <= m; exp *= 10) {
        // 对数组元素的第 k 位执行计数排序
        // k = 1 -> exp = 1
        // k = 2 -> exp = 10
        // 即 exp = 10^(k-1)
        countingSortDigit(nums, exp);
    }
}

为什么从最低位开始排序❓

在连续的排序轮次中，后一轮排序会覆盖前一轮排序的结果。举例来说，如果第一轮排序结果 𝑎<𝑏 ，而第二轮排序结果 𝑎>𝑏 ，那么第二轮的结果将取代第一轮的结果。由于数字的高位优先级高于低位，因此应该先排序低位再排序高位。

4.算法分析

• 稳定性：稳定
• 时间复杂度：最佳：𝑂(𝑛×𝑘) 最差：𝑂(𝑛×𝑘) 平均：𝑂(𝑛×𝑘)
• 空间复杂度：𝑂(𝑛×𝑘)

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶
• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值

小结

重点回顾

• 冒泡排序通过交换相邻元素来实现排序。通过添加一个标志位来实现提前返回，我们可以将冒泡排序的最佳时间复杂度优化到 𝑂(𝑛) 。
• 插入排序每轮将未排序区间内的元素插入到已排序区间的正确位置，从而完成排序。虽然插入排序的时间复杂度为 𝑂(𝑛2) ，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。
• 快速排序基于哨兵划分操作实现排序。在哨兵划分中，有可能每次都选取到最差的基准数，导致时间复杂度劣化至 𝑂(𝑛2) 。引入中位数基准数或随机基准数可以降低这种劣化的概率。尾递归方法可以有效地减少递归深度，将空间复杂度优化到 𝑂(log⁡𝑛) 。
• 归并排序包括划分和合并两个阶段，典型地体现了分治策略。在归并排序中，排序数组需要创建辅助数组，空间复杂度为 𝑂(𝑛) ；然而排序链表的空间复杂度可以优化至 𝑂(1) 。
• 桶排序包含三个步骤：数据分桶、桶内排序和合并结果。它同样体现了分治策略，适用于数据体量很大的情况。桶排序的关键在于对数据进行平均分配。
• 计数排序是桶排序的一个特例，它通过统计数据出现的次数来实现排序。计数排序适用于数据量大但数据范围有限的情况，并且要求数据能够转换为正整数。
• 基数排序通过逐位排序来实现数据排序，要求数据能够表示为固定位数的数字。
• 总的来说，我们希望找到一种排序算法，具有高效率、稳定、原地以及正向自适应性等优点。然而，正如其他数据结构和算法一样，没有一种排序算法能够同时满足所有这些条件。在实际应用中，我们需要根据数据的特性来选择合适的排序算法。
• 下图对比了主流排序算法的效率、稳定性、就地性和自适应性等。

2. Q & A

Q：排序算法稳定性在什么情况下是必需的？

在现实中，我们有可能基于对象的某个属性进行排序。例如，学生有姓名和身高两个属性，我们希望实现一个多级排序：先按照姓名进行排序，得到 (A, 180) (B, 185) (C, 170) (D, 170) ；再对身高进行排序。由于排序算法不稳定，因此可能得到 (D, 170) (C, 170) (A, 180) (B, 185) 。

可以发现，学生 D 和 C 的位置发生了交换，姓名的有序性被破坏了，而这是我们不希望看到的。

Q：哨兵划分中“从右往左查找”与“从左往右查找”的顺序可以交换吗？

不行，当我们以最左端元素为基准数时，必须先“从右往左查找”再“从左往右查找”。这个结论有些反直觉，我们来剖析一下原因。

哨兵划分 partition() 的最后一步是交换 nums[left] 和 nums[i] 。完成交换后，基准数左边的元素都 <= 基准数，这就要求最后一步交换前 nums[left] >= nums[i] 必须成立。假设我们先“从左往右查找”，那么如果找不到比基准数更大的元素，则会在 i == j 时跳出循环，此时可能 nums[j] == nums[i] > nums[left]。也就是说，此时最后一步交换操作会把一个比基准数更大的元素交换至数组最左端，导致哨兵划分失败。

举个例子，给定数组 [0, 0, 0, 0, 1] ，如果先“从左向右查找”，哨兵划分后数组为 [1, 0, 0, 0, 0] ，这个结果是不正确的。

再深入思考一下，如果我们选择 nums[right] 为基准数，那么正好反过来，必须先“从左往右查找”。

Q：关于尾递归优化，为什么选短的数组能保证递归深度不超过 log⁡𝑛 ？

递归深度就是当前未返回的递归方法的数量。每轮哨兵划分我们将原数组划分为两个子数组。在尾递归优化后，向下递归的子数组长度最大为原数组长度的一半。假设最差情况，一直为一半长度，那么最终的递归深度就是 log⁡𝑛 。

回顾原始的快速排序，我们有可能会连续地递归长度较大的数组，最差情况下为 𝑛、𝑛−1、…、2、1 ，递归深度为 𝑛 。尾递归优化可以避免这种情况出现。

Q：当数组中所有元素都相等时，快速排序的时间复杂度是 𝑂(𝑛2) 吗？该如何处理这种退化情况？

是的。对于这种情况，可以考虑通过哨兵划分将数组划分为三个部分：小于、等于、大于基准数。仅向下递归小于和大于的两部分。在该方法下，输入元素全部相等的数组，仅一轮哨兵划分即可完成排序。

Q：桶排序的最差时间复杂度为什么是 𝑂(𝑛2) ？

最差情况下，所有元素被分至同一个桶中。如果我们采用一个 𝑂(𝑛2) 算法来排序这些元素，则时间复杂度为 𝑂(𝑛2) 。

参考文章：

0.1   关于本书 - Hello 算法 (hello-algo.com)

十大经典排序算法总结 | JavaGuide

排序简介 - OI Wiki (oi-wiki.org)

十大经典排序算法动画与解析，看我就够了！（配代码完全版） (qq.com)