排序的基本概念

排序的定义

排序是一种常见的基础算法，其功能是将元素按照特定顺序排列，使得元素有序。排序有广泛的应用，当元素有序时，可以更方便地处理。

排序的分类

排序算法有多种，可以从不同的维度将排序算法分类。

比较类排序和非比较类排序

比较类排序指通过比较元素大小决定元素之间的相对顺序的排序方法。当有 $n$ 个元素需要排序时，比较类排序的时间复杂度下限为 $O(n\log n)$，因此比较类排序也称为非线性时间排序。

非比较类排序指不通过比较元素大小决定元素之间的相对顺序的排序方法。非比较类排序的时间复杂度可以低于比较类排序的时间复杂度下限，达到线性时间复杂度，因此非比较类排序也称为线性时间排序。

内部排序和外部排序

如果待排序元素的数量较少，可以将所有元素存放到内存中执行排序，此时称为内部排序。

如果待排序元素的数量很多，则无法将所有元素同时存放到内存中，需要将元素存放在外存储器中，通过访问外存储器中的元素才能完成排序，此时称为外部排序。

稳定排序和不稳定排序

待排序元素中可能存在相等的情况（或者用于排序的关键字相等）。如果在排序之后，相等元素之间的相对顺序总是保持不变，则排序算法是稳定的。如果在排序之后，相等元素之间的相对顺序可能改变，则排序算法是不稳定的。

不同排序算法的概念和实现

常见的排序算法有 $10$ 种，其中 $7$ 种排序算法是比较类排序算法，$3$ 种排序算法是非比较类排序算法。比较类排序算法又可以分成两大类：$4$ 种排序算法的平均时间复杂度是 $O(n^2)$，称为初级排序算法；$3$ 种排序算法的平均时间复杂度是 $O(n\log n)$，称为高级排序算法。

因此，常见的 $10$ 种排序算法可以分成三大类：

• 初级排序算法，平均时间复杂度是 $O(n^2)$，包括冒泡排序、选择排序、插入排序和希尔排序；
• 高级排序算法，平均时间复杂度是 $O(n\log n)$，包括归并排序、快速排序和堆排序；
• 线性时间排序算法，时间复杂度是线性，包括计数排序、桶排序和基数排序。

说明：希尔排序是插入排序的优化版本，其时间复杂度在 $O(n^{1.25})$ 和 $O(n^2)$ 之间，虽然时间复杂度一般低于 $O(n^2)$，但是高于 $O(n\log n)$，可以认为希尔排序的时间复杂度的一个宽松的上界是 $O(n^2)$，因此将希尔排序归入初级排序算法。

以下介绍 $10$ 种排序算法。在没有特别说明的情况下，默认为升序排序。

初级排序算法

冒泡排序

原理

冒泡排序的原理是多次遍历序列，每次比较相邻的两个元素，如果顺序错误则交换。排序过程中，大的元素会移动到序列的末尾，如同水中的气泡上浮到顶端，故名冒泡排序。

初始时，整个序列都是未排序的序列。每一次遍历序列，未排序的子序列中的最大元素将会移动到该子序列的末尾，使得未排序的子序列的长度减 $1$。当所有元素都移动到正确的位置时，排序结束。

如果在一次遍历序列的过程中没有发现相邻的两个元素顺序错误的情况，则说明所有的元素都在正确的位置，此时可以提前结束排序。这是冒泡排序的一个可以优化的点。

示例

考虑以下序列的冒泡排序：$[6,2,7,1,3,0,8,9,5,4]$。

每一次遍历之后，序列的变化情况如下。

$[2,6,1,3,0,7,8,5,4,9]$

$[2,1,3,0,6,7,5,4,8,9]$

$[1,2,0,3,6,5,4,7,8,9]$

$[1,0,2,3,5,4,6,7,8,9]$

$[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

由于冒泡排序最多需要遍历序列 $n$ 次，每次遍历序列需要 $O(n)$ 的时间，比较操作和交换操作的次数都是 $O(n^2)$，因此冒泡排序的平均时间复杂度和最差时间复杂度都是 $O(n^2)$。

冒泡排序的空间复杂度是 $O(1)$。

稳定性分析

由于冒泡排序每次都是比较相邻的两个元素，只有当相邻的两个元素不相等且顺序错误时才会交换，因此相等元素之间的相对顺序总是保持不变。冒泡排序是稳定的排序算法。

代码

class Solution {
    public void bubbleSort(int[] nums) {
        boolean needNextPass = true;
        int length = nums.length;
        for (int i = 1; i < length && needNextPass; i++) {
            needNextPass = false;
            for (int j = 0; j < length - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    needNextPass = true;
                }
            }
        }
    }
}

选择排序

原理

选择排序的原理是多次遍历序列，每次在未排序的子序列中找到最小元素，将其与该子序列中的首个元素交换。如果未排序的子序列中的最小元素与首个元素相等，则不执行交换操作。

初始时，整个序列都是未排序的序列。每一次遍历序列，未排序的子序列中的最小元素将会移动到该子序列的起始位置，使得已排序的子序列的长度加 $1$，未排序的子序列的长度减 $1$。当所有元素都交换结束时，排序结束。

示例

考虑以下序列的选择排序：$[6,2,7,1,3,0,8,9,5,4]$。

每一次遍历之后，序列的变化情况如下。

$[0,2,7,1,3,6,8,9,5,4]$

$[0,1,7,2,3,6,8,9,5,4]$

$[0,1,2,7,3,6,8,9,5,4]$

$[0,1,2,3,7,6,8,9,5,4]$

$[0,1,2,3,4,6,8,9,5,7]$

$[0,1,2,3,4,5,8,9,6,7]$

$[0,1,2,3,4,5,6,9,8,7]$

$[0,1,2,3,4,5,6,7,8,9]$

$[0,1,2,3,4,5,6,7,8,9]$

$[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

由于选择排序需要执行 $\frac{n(n-1)}{2}$ 次比较操作，最多需要执行 $n-1$ 次交换操作，因此选择排序的平均时间复杂度和最差时间复杂度都是 $O(n^2)$。

选择排序的空间复杂度是 $O(1)$。

稳定性分析

由于选择排序每次交换的元素不一定相邻，因此相等元素之间的相对顺序可能改变。选择排序是不稳定的排序算法。

考虑以下序列的选择排序：$[5,5,4]$。

第一次遍历，将最小的元素 $4$ 与下标 $0$ 处的元素 $5$ 交换，此时序列变成 $[4,5,5]$，已经有序，之后的遍历不会有任何的元素交换。在仅有的一次元素交换中，下标 $0$ 处的 $5$ 交换到下标 $2$ 处，该元素交换前位于下标 $1$ 的元素 $5$ 之前，交换后位于下标 $1$ 的元素 $5$ 之后，因此两个元素 $5$ 的相对顺序改变。

代码

class Solution {
    public void selectionSort(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int currMinIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (nums[j] < nums[currMinIndex]) {
                    currMinIndex = j;
                }
            }
            if (currMinIndex != i) {
                int temp = nums[i];
                nums[i] = nums[currMinIndex];
                nums[currMinIndex] = temp;
            }
        }
    }
}

插入排序

原理

插入排序的原理是维护一个已排序的子序列，每次将一个未排序的元素插入到已排序的子序列中的正确位置。

初始时，只有首个元素为已排序的子序列。每次在已排序的子序列中插入元素时，需要在已排序的子序列中找到比待插入元素大的最小元素，其所在位置即为插入位置。插入元素的具体操作是，将已排序的子序列中从插入位置到子序列末尾的元素都向后移动一位，然后将待插入的元素移动到插入位置。每次插入元素之后，已排序的子序列的长度加 $1$。当已排序的子序列的长度等于整个序列的长度时，排序结束。

示例

考虑以下序列的插入排序：$[6,2,7,1,3,0,8,9,5,4]$。

每一次遍历之后，序列的变化情况如下。

$[2,6,7,1,3,0,8,9,5,4]$

$[2,6,7,1,3,0,8,9,5,4]$

$[1,2,6,7,3,0,8,9,5,4]$

$[1,2,3,6,7,0,8,9,5,4]$

$[0,1,2,3,6,7,8,9,5,4]$

$[0,1,2,3,6,7,8,9,5,4]$

$[0,1,2,3,6,7,8,9,5,4]$

$[0,1,2,3,5,6,7,8,9,4]$

$[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

由于插入排序需要对 $n-1$ 个元素寻找插入位置，对于每个元素，最多需要遍历所有已排序的元素寻找插入位置，因此插入排序的平均时间复杂度和最差时间复杂度都是 $O(n^2)$。

插入排序的空间复杂度是 $O(1)$。

稳定性分析

由于插入排序从左到右依次遍历每个元素，每次插入元素时都是将元素插入到比该元素大的元素左侧，不会将元素插入到和该元素相等的元素左侧，因此相等元素之间的相对顺序总是保持不变。插入排序是稳定的排序算法。

代码

class Solution {
    public void insertionSort(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            int num = nums[i];
            int insertIndex = i;
            for (int j = i - 1; j >= 0 && nums[j] > num; j--) {
                nums[j + 1] = nums[j];
                insertIndex = j;
            }
            if (insertIndex != i) {
                nums[insertIndex] = num;
            }
        }
    }
}

希尔排序

原理

希尔排序由 D. L. Shell 提出，是插入排序的改进版本。为了和希尔排序区分，插入排序有时也称为直接插入排序。

希尔排序也称缩小增量排序，原理是将元素根据下标的增量分组，下标之差为增量的倍数的元素位于同一组，同一组元素使用插入排序。每一轮排序的增量减小，当增量变成 $1$ 时为最后一轮，即插入排序。

希尔排序的时间复杂度取决于增量序列，增量序列的选择应满足增量依次减少且最后一轮的增量必须是 $1$。一种常见的增量序列是：初始增量取 $\lfloor \frac{n}{2}\rfloor$，其余的每个增量都取前一个增量的一半向下取整，直到增量变成 $1$。

当 $n$ 较大时，初始增量较大，分组较多，同一组元素的个数较少且下标差较大，可以快速完成排序，使距离较远的元素相对有序。虽然无法使整个序列完全有序，但是可以使整个序列更接近有序，当增量减小时，排序速度会更快。因此，希尔排序的性能优于插入排序。

示例

考虑以下序列的希尔排序：$[6,2,7,1,3,0,8,9,5,4]$。

序列的长度是 $10$，增量依次取 $5$、$2$、$1$。对于每个增量依次执行排序之后，序列的变化情况如下。

$[0,2,7,1,3,6,8,9,5,4]$

$[0,1,3,2,5,4,7,6,8,9]$

$[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

希尔排序的时间复杂度在 $O(n^{1.25})$ 和 $O(n^2)$ 之间，具体时间复杂度取决于待排序的序列以及增量序列的选取。

希尔排序的空间复杂度是 $O(1)$。

稳定性分析

由于希尔排序每次交换的元素不一定相邻，因此相等元素之间的相对顺序可能改变。希尔排序是不稳定的排序算法。

考虑以下序列的希尔排序：$[5,5,4,8]$。

初始增量是 $2$，下标 $0$ 处的元素 $5$ 与下标 $2$ 处的元素 $4$ 交换位置，此时序列变成 $[4,5,5,8]$，已经有序，之后的排序过程不会有任何的元素交换。在仅有的一次元素交换中，下标 $0$ 处的元素 $5$ 交换到下标 $2$ 处，该元素交换前位于下标 $1$ 的元素 $5$ 之前，交换后位于下标 $1$ 的元素 $5$ 之后，因此两个元素 $5$ 的相对顺序改变。

代码

class Solution {
    public void shellSort(int[] nums) {
        int length = nums.length;
        for (int inc = length / 2; inc > 0; inc /= 2) {
            for (int i = inc; i < length; i++) {
                int num = nums[i];
                int insertIndex = i;
                for (int j = i - inc; j >= 0 && nums[j] > num; j -= inc) {
                    nums[j + inc] = nums[j];
                    insertIndex = j;
                }
                if (insertIndex != i) {
                    nums[insertIndex] = num;
                }
            }
        }
    }
}

高级排序算法

归并排序

原理

归并排序是分治算法的一个典型应用。首先将原序列拆分成多个不相交的子序列，对每个子序列排序，然后将有序子序列合并，合并过程中确保合并后的子序列仍然有序。合并结束之后，整个序列排序结束。将两个有序子序列合并成一个有序子序列的操作称为归并，基于归并算法的排序算法称为归并排序。

归并排序可以使用自顶向下的方式递归实现，也可以使用自底向上的方式迭代实现。对于同一个序列，使用自顶向下和自底向上两种方式实现的中间过程可能有所区别，但是都能得到正确的排序结果。

自顶向下的实现过程如下。

1. 如果当前序列的长度大于 $1$，则将当前序列拆分成长度之差不超过 $1$ 的两个子序列，如果子序列的长度大于 $1$ 则继续将子序列拆分成更短的子序列，直到子序列的长度等于 $1$。
2. 对每个子序列分别排序，然后将排序后的子序列合并，合并过程中确保合并后的子序列仍然有序。当所有元素都合并结束时，排序结束。

自底向上的实现过程如下。

1. 初始时半子序列长度是 $1$，子序列长度是 $2$。将每个子序列中的两个半子序列合并，合并过程中确保合并后的子序列仍然有序。如果最后一个子序列的长度不超过半子序列长度，则忽略最后一个子序列。
2. 将半子序列长度和子序列长度都乘以 $2$，重复上述合并操作。当所有元素都合并结束时，排序结束。

示例

考虑以下序列的归并排序：$[6,2,7,1,3,0,8,9,5,4]$。

1. 自顶向下

   序列拆分情况如下。

   $[[6,2,7,1,3],[0,8,9,5,4]]$

   $[[[6,2,7],[1,3]],[[0,8,9],[5,4]]]$

   $[[[[6,2],[7]],[[1],[3]]],[[[0,8],[9]],[[5],[4]]]]$

   $[[[[[6],[2]],[7]],[[1],[3]]],[[[[0],[8]],[9]],[[5],[4]]]]$

   序列归并情况如下。

   $[[[[2,6],[7]],[1,3]],[[[0,8],[9]],[4,5]]]$

   $[[[2,6,7],[1,3]],[[0,8,9],[4,5]]]$

   $[[1,2,3,6,7],[0,4,5,8,9]]$

   $[0,1,2,3,4,5,6,7,8,9]$

2. 自顶向上

   序列归并情况如下。

   $[[6],[2],[7],[1],[3],[0],[8],[9],[5],[4]]$

   $[[2,6],[1,7],[0,3],[8,9],[4,5]]$

   $[[1,2,6,7],[0,3,8,9],[4,5]]$

   $[[0,1,2,3,6,7,8,9],[4,5]]$

   $[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

用 $T(n)$ 表示对 $n$ 个元素归并排序的时间。由于归并排序每次将待排序的序列拆分成两个子序列，对两个子序列分别递归排序，然后使用 $O(n)$ 的时间将两个有序的子序列合并，因此有 $T(n)=2T\left(\frac{n}{2}\right)+O(n)$，根据主定理可以得到 $T(n)=O(n\log n)$。因此归并排序的平均时间复杂度和最差时间复杂度都是 $O(n\log n)$。

自顶向下实现时需要递归调用栈的空间是 $O(\log n)$，自底向上实现时可以省略递归调用栈的空间。无论是自顶向下实现还是自底向上实现，归并过程需要 $O(n)$ 的辅助空间。因此归并排序的空间复杂度是 $O(n)$。

稳定性分析

由于归并排序只有在合并两个子序列时才可能改变元素之间的相对顺序，且只有当左边的元素大于右边的元素时才会改变这两个元素的相对顺序，因此相等元素之间的相对顺序总是保持不变。归并排序是稳定的排序算法。

代码

以下代码为归并排序的自顶向下实现。

class Solution {
    public void mergeSort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    public void sort(int[] nums, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            sort(nums, low, mid);
            sort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }
    }

    public void merge(int[] nums, int low, int mid, int high) {
        int currLength = high - low + 1;
        int[] temp = new int[currLength];
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        System.arraycopy(temp, 0, nums, low, currLength);
    }
}

以下代码为归并排序的自底向上实现。

class Solution {
    public void mergeSort(int[] nums) {
        int length = nums.length;
        for (int halfLength = 1, currLength = 2; halfLength < length; halfLength *= 2, currLength *= 2) {
            for (int low = 0; low < length - halfLength; low += currLength) {
                int mid = low + halfLength - 1;
                int high = Math.min(low + currLength - 1, length - 1);
                merge(nums, low, mid, high);
            }
        }
    }

    public void merge(int[] nums, int low, int mid, int high) {
        int currLength = high - low + 1;
        int[] temp = new int[currLength];
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        System.arraycopy(temp, 0, nums, low, currLength);
    }
}

快速排序

原理

快速排序是利用分治思想的排序算法。其原理是在待排序的序列中选择一个基准元素，使用基准元素将序列分区，然后对分区后的两个子序列排序。当每个子序列都排序结束时，整个序列排序结束。

快速排序的操作包括选择基准元素和分区，只有当序列的长度大于 $1$ 时才需要选择基准元素和分区。选择基准元素和分区的操作如下。

1. 选择基准元素。可以选择序列的首个元素作为基准元素，也可以在序列中随机选择一个元素作为基准元素并将基准元素与序列的首个元素交换位置，此时序列的首个元素为基准元素。
2. 分区。分区的含义是将序列分成两个子序列，基准元素左侧子序列的元素都小于等于基准元素，基准元素右侧子序列的元素都大于基准元素。具体做法如下。
   1. 用 $\text{start}$ 和 $\text{end}$ 分别表示当前序列的开始下标和结束下标，初始化两个指针 $\text{low}=\text{start}+1$ 和 $\text{high}=\text{end}$。
   2. 将 $\text{low}$ 从左往右遍历，直到遇到大于基准元素的元素；将 $\text{high}$ 从右往左遍历，直到遇到小于等于基准元素的元素。此时如果 $\text{low}<\text{high}$，则交换 $\text{low}$ 和 $\text{high}$ 处的元素。重复该操作，直到 $\text{low}\ge \text{high}$ 时结束该操作。
   3. 将 $\text{high}$ 从右往左遍历，直到遇到小于等于基准元素的元素。
   4. 此时 $\text{high}$ 指向基准元素应该放置下标的位置。如果 $\text{high}>\text{start}$，则交换 $\text{start}$ 和 $\text{high}$ 处的元素。
3. 使用同样的方法对基准元素左右两侧的两个子序列排序，直到子序列的长度不超过 $1$ 时，不需要继续分区。

示例

考虑以下序列的快速排序：$[6,2,7,1,3,0,8,9,5,4]$。

快速排序过程中，每次选择子序列的首个元素作为基准元素。序列的变化情况和分区情况如下。

$[[5,2,4,1,3,0],6,[9,8,7]]$

$[[0,2,4,1,3],5,6,[9,8,7]]$

$[0,[2,4,1,3],5,6,[9,8,7]]$

$[0,1,2,[4,3],5,6,[9,8,7]]$

$[0,1,2,3,4,5,6,[9,8,7]]$

$[0,1,2,3,4,5,6,[7,8],9]$

$[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

快速排序中每次分区的时间复杂度是 $O(n)$，总时间复杂度和递归调用层数有关。平均情况下，递归调用层数是 $O(\log n)$，快速排序的时间复杂度是 $O(n\log n)$。最差情况下，每次分区时选择的基准元素都是序列中的最小值或最大值，递归调用层数是 $O(n)$，快速排序的时间复杂度是 $O(n^2)$。

空间复杂度取决于递归调用层数。平均情况下，递归调用层数是 $O(\log n)$，快速排序的空间复杂度是 $O(\log n)$。最差情况下，递归调用层数是 $O(n)$，快速排序的空间复杂度是 $O(n)$。

稳定性分析

由于快速排序每次交换的元素不一定相邻，因此相等元素之间的相对顺序可能改变。快速排序是不稳定的排序算法。

考虑以下序列的快速排序：$[5,5,4,8]$。

选择首个元素 $5$ 作为基准元素，基准元素与下标 $2$ 处的元素 $4$ 交换位置，此时序列变成 $[4,5,5,8]$，已经有序，之后的排序过程不会有任何的元素交换。在仅有的一次元素交换中，下标 $0$ 处的元素 $5$ 交换到下标 $2$ 处，该元素交换前位于下标 $1$ 的元素 $5$ 之前，交换后位于下标 $1$ 的元素 $5$ 之后，因此两个元素 $5$ 的相对顺序改变。

代码

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

    public void sort(int[] nums, int start, int end) {
        if (start < end) {
            int pivotIndex = partition(nums, start, end);
            sort(nums, start, pivotIndex - 1);
            sort(nums, pivotIndex + 1, end);
        }
    }

    public int partition(int[] nums, int start, int end) {
        int randomIndex = start + (int) (Math.random() * (end - start + 1));
        swap(nums, start, randomIndex);
        int pivot = nums[start];
        int low = start + 1, high = end;
        while (low < high) {
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            while (low < high && nums[high] > pivot) {
                high--;
            }
            if (low < high) {
                swap(nums, low, high);
            }
        }
        while (high > start && nums[high] > pivot) {
            high--;
        }
        if (high > start) {
            swap(nums, start, high);
        }
        return high;
    }

    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

堆排序

原理

堆排序是利用二叉堆实现的排序算法。二叉堆是一个完全二叉树，其中的元素按照特定规则排列。升序排序利用的是大根堆，大根堆中的每个结点元素都大于其子结点元素，根结点元素是堆中最大的。

堆排序的原理是用待排序的序列中的所有元素构建大根堆，将根结点元素与末尾元素交换，此时末尾元素即为最大元素，为已排序的元素，然后将其余未排序的元素重新构成大根堆并重复排序过程。当所有元素都变成已排序的元素时，排序结束。

由于二叉堆是完全二叉树，因此二叉堆可以使用数组表示。使用数组表示二叉堆时，下标 $0$ 处的元素为二叉堆的根结点元素，下标 $i$ 处的元素的左子结点和右子结点的下标分别是 $2\times i+1$ 和 $2\times i+2$。

对于长度为 $n$ 的序列，初始时 $n$ 个元素都位于大根堆中，下标 $0$ 处的元素为最大元素。将下标 $0$ 处的元素与下标 $n-1$ 处的元素交换，此时下标 $n-1$ 处的元素为最大元素且已经到正确的位置，大根堆中剩余 $n-1$ 个未排序的元素，对大根堆中剩余的元素继续维护大根堆的性质并完成排序。

在构建大根堆和排序过程中可能出现不符合大根堆的性质的情况，此时需要调整元素使得元素之间符合大根堆的性质。用 $x$ 表示待调整的元素，调整方法是：如果 $x$ 小于至少一个子结点元素，则将 $x$ 和较大的子结点元素交换，其效果是较大的子结点元素上浮，$x$ 下沉，然后比较 $x$ 与新的子结点元素之间的大小关系并重复上述过程，直到 $x$ 到达叶结点或者大于等于全部子结点元素。

示例

考虑以下序列的堆排序：$[6,2,7,1,3,0,8,9,5,4]$。

将每个元素按照原序列中的顺序依次加入大根堆，得到的大根堆是：$[9,6,8,5,4,0,7,1,2,3]$。

每一轮堆排序，首先将根结点元素与未排序元素中的末尾元素交换，使得未排序元素的个数减 $1$，然后将未排序元素调整，使得元素之间符合大根堆的性质。序列的变化情况如下。

$[8,6,7,5,4,0,3,1,2,9]$

$[7,6,3,5,4,0,2,1,8,9]$

$[6,5,3,1,4,0,2,7,8,9]$

$[5,4,3,1,2,0,6,7,8,9]$

$[4,2,3,1,0,5,6,7,8,9]$

$[3,2,0,1,4,5,6,7,8,9]$

$[2,1,0,3,4,5,6,7,8,9]$

$[1,0,2,3,4,5,6,7,8,9]$

$[0,1,2,3,4,5,6,7,8,9]$

复杂度分析

当二叉堆有 $n$ 个元素时，高度是 $O(\log n)$，每次调整元素需要 $O(\log n)$ 的时间，因此构建大根堆需要 $O(n\log n)$ 的时间。排序过程中，每次将一个元素与未排序元素中的末尾元素交换之后调整元素需要 $O(\log n)$ 的时间，因此排序过程需要 $O(n\log n)$ 的时间。堆排序的平均时间复杂度和最差时间复杂度都是 $O(n\log n)$。

堆排序的空间复杂度是 $O(1)$。

稳定性分析

由于堆排序每次交换的元素不一定相邻，因此相等元素之间的相对顺序可能改变。堆排序是不稳定的排序算法。

考虑以下序列的堆排序：$[5,5,4]$。

该序列已经符合大顶堆，下标 $0$ 处的元素 $5$ 已经是最大元素。下标 $0$ 处的元素 $5$ 与下标 $2$ 处的元素 $4$ 交换位置，此时序列变成 $[4,5,5]$，下标 $2$ 处的元素 $5$ 不会与任何元素交换。在这次元素交换中，下标 $0$ 处的 $5$ 交换到下标 $2$ 处，该元素交换前位于下标 $1$ 的元素 $5$ 之前，交换后位于下标 $1$ 的元素 $5$ 之后，因此两个元素 $5$ 的相对顺序改变。

代码

class Solution {
    public void heapSort(int[] nums) {
        int length = nums.length;
        for (int i = length / 2; i >= 0; i--) {
            sink(nums, i, length);
        }
        for (int i = length - 1; i > 0; i--) {
            swap(nums, 0, i);
            sink(nums, 0, i);
        }
    }

    public void sink(int[] nums, int currIndex, int length) {
        for (int i = currIndex * 2 + 1; i < length; i = i * 2 + 1) {
            if (i + 1 < length && nums[i] < nums[i + 1]) {
                i++;
            }
            if (nums[i] <= nums[currIndex]) {
                break;
            }
            swap(nums, currIndex, i);
            currIndex = i;
        }
    }

    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

线性时间排序算法

计数排序

原理

计数排序的原理是统计每个元素在序列中出现的次数，然后根据出现次数将元素存储在排序后的下标位置。因此计数排序要求元素必须是有确定范围的整数。

计数排序的实现过程如下。

1. 遍历序列，得到序列中的最大值和最小值，计算序列中的元素范围。
2. 创建计数数组，其长度等于元素范围。遍历序列，在计数数组中记录每个元素在序列中出现的次数。每个元素在计数数组中对应的下标为元素值平移之后的结果，平移的含义是将元素值减去最小值，最小值在计数数组中对应的下标为 $0$。
3. 将计数数组转换成前缀和数组，前缀和数组中的每个下标处的计数表示不超过特定元素的元素个数（特定元素等于前缀和数组中对应的下标平移回去的结果）。
4. 创建与原序列长度相同的有序序列用于存储排序后的元素。反向遍历原序列，将原序列中的每个元素填到有序序列中的正确下标处。
   1. 当一个元素在前缀和数组中对应的计数为 $x$ 时，表示不超过该元素的值有 $x$ 个，因此该元素在有序序列中应该存放的下标位置是 $\text{index}=x-1$，将该元素填到有序序列中的下标 $\text{index}$ 处。
   2. 将该元素填到有序序列中之后，将前缀和数组中该元素对应的计数减 $1$。

当所有元素都填到有序序列中之后，排序结束。

示例

考虑以下序列的计数排序：$[0,5,3,3,-2,-3,-5,0,-5,2]$。

最大值是 $5$，最小值是 $-5$，元素范围是 $11$ 个元素。

将每个元素减去最小值之后计算每个元素在序列中出现的次数，得到计数数组：$[2,0,1,1,0,2,0,1,2,0,1]$。

将计数数组转换成前缀和数组：$[2,2,3,4,4,6,6,7,9,9,10]$。

反向遍历原序列，对于每个元素更新有序序列与前缀和数组。有序序列与前缀和数组的变化情况如下，有序序列中的下划线表示尚未填入元素。

$[\_,\_,\_,\_,\_,\_,2,\_,\_,\_],[2,2,3,4,4,6,6,6,9,9,10]$

$[\_,-5,\_,\_,\_,\_,2,\_,\_,\_],[1,2,3,4,4,6,6,6,9,9,10]$

$[\_,-5,\_,\_,\_,0,2,\_,\_,\_],[1,2,3,4,4,5,6,6,9,9,10]$

$[-5,-5,\_,\_,\_,0,2,\_,\_,\_],[0,2,3,4,4,5,6,6,9,9,10]$

$[-5,-5,-3,\_,\_,0,2,\_,\_,\_],[0,2,2,4,4,5,6,6,9,9,10]$

$[-5,-5,-3,-2,\_,0,2,\_,\_,\_],[0,2,2,3,4,5,6,6,9,9,10]$

$[-5,-5,-3,-2,\_,0,2,\_,3,\_],[0,2,2,3,4,5,6,6,8,9,10]$

$[-5,-5,-3,-2,\_,0,2,3,3,\_],[0,2,2,3,4,5,6,6,7,9,10]$

$[-5,-5,-3,-2,\_,0,2,3,3,5],[0,2,2,3,4,5,6,6,7,9,9]$

$[-5,-5,-3,-2,0,0,2,3,3,5],[0,2,2,3,4,4,6,6,7,9,9]$

复杂度分析

假设元素范围包括 $k$ 个不同的元素。计数排序需要 $O(n)$ 的时间寻找最大值和最小值、计算元素范围和统计元素出现的次数，需要 $O(k)$ 的时间计算计数数组的前缀和数组，以及需要 $O(n)$ 的时间将元素填入有序序列，因此计数排序的平均时间复杂度和最差时间复杂度都是 $O(n+k)$。

计数排序需要创建有序序列存储排序后的元素以及需要创建计数数组统计元素出现的次数（前缀和数组为计数数组的复用），因此计数排序的空间复杂度是 $O(n+k)$。

稳定性分析

计数排序的排序过程为反向遍历原序列并将原序列中的每个元素填到有序序列中的正确下标处。对于相等的元素，填到有序序列中的顺序是从后往前，和反向遍历原序列的过程中遍历元素的顺序相同，因此相等元素之间的相对顺序总是保持不变。计数排序是稳定的排序算法。

代码

class Solution {
    public void countingSort(int[] nums) {
        int length = nums.length;
        int minNum = nums[0], maxNum = nums[0];
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        int offset = minNum;
        int interval = maxNum - minNum + 1;
        int[] counts = new int[interval];
        for (int num : nums) {
            counts[num - offset]++;
        }
        for (int i = 1; i < interval; i++) {
            counts[i] += counts[i - 1];
        }
        int[] sorted = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            int num = nums[i];
            int index = counts[num - offset] - 1;
            sorted[index] = num;
            counts[num - offset]--;
        }
		System.arraycopy(sorted, 0, nums, 0, length);
    }
}

桶排序

原理

桶排序的原理是将序列中的元素分到多个桶内，对每个桶内的元素分别排序，最后将每个桶内的有序元素合并，即可得到排序后的序列。

桶排序需要预先设定桶的大小（即每个桶最多包含的不同元素个数）和桶的个数，将元素按照元素值均匀分布到各个桶内。对于每个元素，根据该元素与最小元素之差以及桶的大小计算该元素应该分到的桶的编号，可以确保编号小的桶内的元素都小于编号大的桶内的元素。当所有元素都分到桶内之后，对于每个桶分别排序，由于每个桶内的元素个数较少，因此每个桶的排序可以使用插入排序实现。当每个桶都排序结束之后，按照桶的编号从小到大的顺序依次取出每个桶内的元素，拼接之后得到的序列即为排序后的序列。

示例

考虑以下序列的桶排序：$[44,10,13,38,12,25,19,22,50,39]$。

最大值是 $50$，最小值是 $10$。将每个桶的大小设为 $10$（即每个桶最多包含 $10$ 个不同元素），则可以将所有元素分成 $5$ 个桶：

$0:[10,13,12,19]$

$1:[25,22]$

$2:[38,39]$

$3:[44]$

$4:[50]$

对于每个桶分别排序：

$0:[10,12,13,19]$

$1:[22,25]$

$2:[38,39]$

$3:[44]$

$4:[50]$

依次拼接每个桶内的元素，即可得到排序后的序列：

$[10,12,13,19,22,25,38,39,44,50]$

复杂度分析

假设有 $k$ 个桶。平均情况下，每个桶内的元素个数较少，因此时间复杂度主要取决于将元素分到桶内和拼接每个桶的元素的时间，桶排序的时间复杂度是 $O(n+k)$。最差情况下，多个元素被分到同一个桶内，对于这个桶排序的时间复杂度是 $O(n^2)$，桶排序的时间复杂度是 $O(n^2)$。

桶排序需要创建 $k$ 个桶存放全部元素，因此桶排序的空间复杂度是 $O(n+k)$。

稳定性分析

桶排序的排序过程包括将元素分到桶内、对每个桶分别排序和拼接排序后的结果，其中只有对每个桶分别排序会改变元素之间的相对顺序。只要对每个桶分别排序时使用稳定的排序算法，就能确保相等元素之间的相对顺序总是保持不变，此时桶排序是稳定的排序算法。

代码

class Solution {
    static final int BUCKET_SIZE = 100;

    public void bucketSort(int[] nums) {
        int minNum = nums[0], maxNum = nums[0];
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        int bucketCount = (maxNum - minNum) / BUCKET_SIZE + 1;
        List<Integer>[] buckets = new List[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<Integer>();
        }
        for (int num : nums) {
            int bucketIndex = (num - minNum) / BUCKET_SIZE;
            buckets[bucketIndex].add(num);
        }
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            List<Integer> bucket = buckets[i];
            sort(bucket);
            for (int num : bucket) {
                nums[index++] = num;
            }
        }
    }

    public void sort(List<Integer> bucket) {
        int size = bucket.size();
        for (int i = 1; i < size; i++) {
            int num = bucket.get(i);
            int insertIndex = i;
            for (int j = i - 1; j >= 0 && bucket.get(j) > num; j--) {
                bucket.set(j + 1, bucket.get(j));
                insertIndex = j;
            }
            if (insertIndex != i) {
                bucket.set(insertIndex, num);
            }
        }
    }
}

基数排序

原理

基数排序的原理是基于关键字对元素排序。当元素有多个关键字时，需要执行多轮排序，每一轮基于一个关键字排序，使用关键字的顺序是从最低关键字到最高关键字。例如，使用基数排序对数字序列排序时，依次按照最低有效位到最高有效位的顺序对数字序列排序。

为了确保基数排序的结果正确，每一轮基于一个关键字排序时必须使用稳定排序。基于一个关键字排序时，常用的方法是计数排序。

基数排序的实现过程如下。

1. 由于待排序的序列中可能有负数，为了方便处理，需要首先得到序列中的最大值和最小值，计算序列中的元素范围，并将序列中的每个元素平移，平移的含义是将元素值减去最小值，最小值平移之后变成 $0$。
2. 根据平移之后的最大值，可以得到平移之后的元素值的最大长度，即每个元素的有效位数。
3. 依次按照最低有效位到最高有效位的顺序，对序列使用计数排序的方法排序。
4. 排序结束之后，将序列中的每个元素反向平移得到原始的元素排序之后的序列。

基数排序一般基于十进制，也可以基于非十进制。

示例

考虑以下序列的基数排序：$[379,979,118,716,945,441,121,194,248,775]$。

最大值是 $979$，最小值是 $118$。将序列中的每个元素平移之后，得到序列：$[261,861,0,598,827,323,3,76,130,657]$。平移之后的最大值是 $861$，是三位数，因此有三个有效位。

依次按照最低有效位到最高有效位的顺序排序。序列的变化情况如下。

$[0,130,261,861,323,3,76,827,657,598]$

$[0,3,323,827,130,657,261,861,76,598]$

$[0,3,76,130,261,323,598,657,827,861]$

排序结束之后，将序列中的每个元素反向平移得到原始的元素排序之后的序列：

$[118,121,194,248,379,441,716,775,945,979]$

复杂度分析

假设基数排序基于 $k$ 进制，每个元素最多有 $d$ 个有效位。基于一个有效位使用计数排序需要 $O(n+k)$ 的时间，需要对 $d$ 个有效位分别执行计数排序，因此基数排序的平均时间复杂度和最差时间复杂度都是 $O(d(n+k))$。

基于每个有效位的计数排序需要 $O(n+k)$ 的空间，因此基数排序的空间复杂度是 $O(n+k)$。

稳定性分析

基数排序的实现为依次按照最低有效位到最高有效位的顺序使用计数排序。由于计数排序是稳定的排序算法，不会改变相等元素之间的相对顺序，因此基数排序的过程中，相等元素之间的相对顺序总是保持不变。基数排序是稳定的排序算法。

代码

class Solution {
    static final int RADIX = 10;

    public void radixSort(int[] nums) {
        int length = nums.length;
        int minNum = nums[0], maxNum = nums[0];
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        int maxDigitCount = getDigitCount(maxNum - minNum);
        for (int i = 0; i < length; i++) {
            nums[i] -= minNum;
        }
        for (int digitCount = 1, unit = 1; digitCount <= maxDigitCount; digitCount++, unit *= RADIX) {
            sort(nums, unit);
        }
        for (int i = 0; i < length; i++) {
            nums[i] += minNum;
        }
    }

    public int getDigitCount(int num) {
        int digitCount = 0;
        while (num > 0) {
            num /= RADIX;
            digitCount++;
        }
        return digitCount;
    }

    public void sort(int[] nums, int unit) {
        int length = nums.length;
        int[] counts = new int[RADIX];
        for (int num : nums) {
            int digit = num % (unit * RADIX) / unit;
            counts[digit]++;
        }
        for (int i = 1; i < RADIX; i++) {
            counts[i] += counts[i - 1];
        }
        int[] sorted = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            int num = nums[i];
            int digit = num % (unit * RADIX) / unit;
            int index = counts[digit] - 1;
            sorted[index] = num;
            counts[digit]--;
        }
        System.arraycopy(sorted, 0, nums, 0, length);
    }
}

Java 自带的排序方法

Java 自带的 $\text{Arrays}$ 类和 $\text{Collections}$ 类都有静态方法 $\text{sort}$，该方法对数组或列表排序。

Arrays.sort 实现原理

$\text{Arrays.sort}$ 可以对整个数组或者数组的特定下标范围排序。当参数只有数组时，对整个数组排序；当参数有数组、开始下标和结束下标时，对数组的指定下标范围排序。

根据待排序数组的数据类型是基本数据类型或引用数据类型，其实现原理也不同。

基本数据类型数组排序

当数组中的元素类型是基本数据类型时，除了布尔类型以外都可以排序。对于基本数据类型数组的排序，$\text{Arrays.sort}$ 方法将调用 $\text{DualPivotQuicksort.sort}$ 方法，该方法根据数组中待排序部分的长度（为了表述方便，以下统一用数组长度表示）决定使用的排序算法。

具体而言，数组长度与使用的排序算法之间的关系如下：

• 当数组长度小于 $47$ 时，使用插入排序；
• 当数组长度大于等于 $47$ 且小于 $286$ 时，使用快速排序；
• 当数组长度大于等于 $286$ 且数组基本有序时，使用归并排序；
• 当数组长度大于等于 $286$ 且数组基本无序时，使用快速排序。

当有 $n$ 个元素需要排序时，可以认为 $\text{Arrays.sort}$ 的时间复杂度是 $O(n\log n)$，空间复杂度是 $O(\log n)$。

引用数据类型数组排序

当数组中的元素类型是引用数据类型时，待排序的数组是 $\text{Object}$ 数组。

对引用数据类型数组排序时，必须至少满足以下两个条件之一，否则会抛异常：

• 数组元素的类型实现 $\text{Comparable}$ 接口；
• 排序时传入 $\text{Comparator}$ 接口的对象。

JDK 8 会默认选择 TimSort 作为排序算法。TimSort 是一种起源于归并排序和插入排序的混合排序算法，以归并排序为主，在小片段的合并中使用插入排序。

Collections.sort 实现原理

$\text{Collections.sort}$ 可以对列表排序，其底层实现调用 $\text{Arrays.sort}$。由于列表中存储的元素都是引用数据类型，因此使用 TimSort 作为排序算法。

总结

$\text{Arrays.sort}$ 和 $\text{Collections.sort}$ 的底层实现都是数组的排序。当数组中的元素类型是基本数据类型时，底层实现使用的排序算法有快速排序、归并排序和插入排序；当数组中的元素类型是引用数据类型时，底层实现使用的排序算法有归并排序和插入排序。

使用不同的排序算法的原因是考虑到快速排序和归并排序的两点不同之处：

• 虽然快速排序和归并排序的平均时间复杂度相同，但是大多数情况下快速排序的运行速度快于归并排序，只有当数组基本有序时，归并排序的运行速度快于快速排序；
• 快速排序是不稳定的排序算法，归并排序是稳定的排序算法。

对于基本数据类型数组的排序，只需要考虑元素本身的大小关系，因此排序算法的稳定性不会影响排序结果，使用快速排序可以提升排序速度。对于引用数据类型数组的排序，元素之间的比较依据是可以自定义的，可能只是比较元素的一个属性，因此应该确保排序算法的稳定性，确保其他属性的顺序不会因为排序而改变。

目录

1. 排序实现题目：排序数组
2. 排序实现题目：对链表进行插入排序
3. 排序实现题目：排序链表
4. 排序题目：判断能否形成等差数列
5. 排序题目：最小绝对差
6. 排序题目：高度检查器
7. 排序题目：删除某些元素后的数组均值
8. 排序题目：多数元素
9. 排序题目：有效的字母异位词
10. 排序题目：第三大的数
11. 排序题目：数组中两元素的最大乘积
12. 排序题目：有序数组的平方
13. 排序题目：丢失的数字
14. 排序题目：找不同
15. 排序题目：多数元素 II
16. 排序题目：三个数的最大乘积
17. 排序题目：错误的集合
18. 排序题目：最小时间差
19. 排序题目：相对名次
20. 排序题目：最短无序连续子数组
21. 排序题目：通过翻转子数组使两个数组相等
22. 排序题目：数组的相对排序
23. 排序题目：按照频率将数组升序排序
24. 排序题目：根据字符出现频率排序
25. 排序题目：数组序号转换
26. 排序题目：两点之间不包含任何点的最宽垂直面积
27. 排序题目：重新排列日志文件
28. 排序题目：餐厅过滤器
29. 排序题目：字母异位词分组
30. 排序题目：检查一个字符串是否可以打破另一个字符串
31. 排序题目：警告一小时内使用相同员工卡大于等于三次的人
32. 排序题目：颜色分类
33. 排序题目：合并区间
34. 排序题目：插入区间
35. 排序题目：删除被覆盖区间
36. 排序题目：一手顺子
37. 排序题目：H 指数
38. 排序题目：三次操作后最大值与最小值的最小差
39. 排序题目：将矩阵按对角线排序
40. 排序题目：对角线遍历 II
41. 排序题目：重新排列后的最大子矩阵
42. 排序题目：翻转对
43. 排序题目：区间和的个数
44. 排序题目：计算右侧小于当前元素的个数
45. 排序题目：通过指令创建有序数组
46. 排序题目：最大间距
47. 排序题目：检查字符串是否可以通过排序子字符串得到另一个字符串