Java算法 — 快速排序（Quick Sort）

type

status

date

urlname

summary

快速排序（Quick Sort）

💡

快速排序中的分区操作是算法的核心部分，它决定了整个排序过程的效率。分区操作的主要目的是将数组分为两个部分，使得左边部分的所有元素都不大于基准值（pivot），而右边部分的所有元素都不小于基准值。以下是分区操作的一个常见实现细节：

‌选择基准值‌：首先，从数组中选取一个元素作为基准值。选择基准值的方法有多种，如选择数组的第一个元素、最后一个元素、中间元素，或者是三数中值分割法（选择第一个、中间、最后一个元素的中位数作为基准值）等。

‌设置指针‌：设置两个指针，通常称为i（指向当前考察的元素）和j（从数组末尾开始向前搜索）。初始时，i指向基准值的前一个位置（即基准值左边的第一个位置），j指向数组的末尾。

‌开始分区‌：

从数组的末尾开始，将j指针向前移动，直到找到一个小于或等于基准值的元素。

然后，将i指针加1，并将j指针所指的元素与i指针所指的元素交换位置。此时，i指针左边的所有元素都小于或等于基准值（但此时并不包括基准值本身，因为基准值还在其原始位置）。

重复上述过程，继续向前移动j指针，直到j小于或等于i为止（此时，所有小于或等于基准值的元素都已经被移动到基准值的左边）。

‌放置基准值‌：在分区过程的最后，将基准值交换到其最终位置（即i所指向的位置）。此时，基准值左边的所有元素都不大于它，右边的所有元素都不小于它。

‌递归排序‌：分区操作完成后，基准值被放置在了正确的位置上，接下来可以递归地对基准值左边和右边的子数组进行快速排序。

这个分区过程的关键在于通过交换元素来确保基准值左边的所有元素都不大于它，右边的所有元素都不小于它。这种分区方式使得快速排序能够高效地对数组进行排序。

代码实现

快速排序的性能分析

‌时间复杂度‌：

平均时间复杂度：O(n log n)，其中n是序列中元素的数量。
最佳时间复杂度：O(n)，这种情况发生在每次分区操作都能将序列分成大小相等的两部分时。
最差时间复杂度：O(n^2)，这种情况发生在序列已经接近有序（或完全逆序）时，每次分区操作只得到一个元素的子序列。

‌空间复杂度‌：根据实现方式的不同而有所不同，递归实现时，空间复杂度主要由递归栈的深度决定，最坏情况下为O(n)。

快速排序的特点

快速排序通常比其他O(n log n)的排序算法（如归并排序）在实际应用中更快，因为其内部循环可以在大多数架构上高效实现。

快速排序不是一种稳定的排序算法，即相等的元素在排序后可能会改变其相对位置。

快速排序对于大多数随机性较强的数据排序表现优异，但在处理顺序性较强的数据（如已排序或接近排序的数据）时性能可能退化。

优点

‌效率高‌：在平均情况下，快速排序的时间复杂度为O(n log n)，这使得它在处理大数据集时非常高效。

‌原地排序‌：快速排序是一种原地排序算法，它只需要极少的额外空间（主要是递归调用栈的空间），在大多数情况下，其空间复杂度为O(log n)。

‌实现简单‌：快速排序的算法思想相对直观，实现起来也比较简单。

缺点

‌不稳定性‌：快速排序是一种不稳定的排序算法，即相等的元素在排序后可能会改变其相对位置。

‌最坏情况性能‌：在最坏情况下，即当输入数组已经有序或接近有序时，快速排序的时间复杂度会退化到O(n^2)。

适用场景

快速排序适用于各种类型的数据排序，特别是当数据量较大时。它广泛应用于数据库索引构建、文件系统排序、编译器优化、财务交易排序、搜索引擎结果排序以及大数据处理等领域。在这些场景中，快速排序能够高效地处理大量数据，提高整体性能。

容易出现的问题

‌递归深度过大‌：当待排序数组很大时，递归调用可能会导致堆栈溢出。

‌分割不平衡‌：在某些情况下，快速排序可能会导致分割不平衡，即划分的两个子数组大小差异很大，从而影响排序性能。

‌重复元素处理‌：如果待排序数组包含大量重复元素，传统的快速排序实现可能会导致时间复杂度达到O(n^2)。

解决方案

‌限制递归深度‌：可以通过非递归实现（如使用迭代）或尾递归优化来减少递归深度，避免堆栈溢出。

‌优化分割策略‌：采用随机选择基准元素、三数取中法或者其他优化策略来避免分割不平衡。

‌处理重复元素‌：可以使用三路快排算法，将数组划分为小于、等于和大于基准元素的三部分，以更高效地处理重复元素。

List.sort()

在JDK中List接口的sort方法应该算是我们最常使用的排序方式了，那么我们在使用它的过程中有没有对它产生过好奇呢？它的底层排序逻辑是怎么样？用的哪个算法？哪些核心思想呢？下面我们来看看它的源码吧

源码

可以看到这是一个默认方法，用于对列表进行排序。接收一个参数C（比较器）Comparator<? super E> 表示可以比较列表中元素的比较器用于比较列表元素的比较器。

如果为 null，则使用元素的自然顺序。它先将列表转换为数组。

然后使用 Arrays.sort 方法对数组进行排序。这里使用了类型转换 (Comparator) c，因为 Arrays.sort 方法需要 Comparator 类型的参数。

最后获取列表的迭代器。遍历排序后的数组，并使用迭代器将排序后的元素设置回列表中

我们可以看到其中最关键的是 Arrays.sort 那我们以此为中心展开说话！！

Arrays.sort() 排序的核心思想主要基于分治法和多种排序算法的结合使用，以达到高效排序的目的。jdk1.8 之前，Arrays.sort() 方法使用的是传统快排的方式进行排序。jdk1.8 后，Arrays.sort() 方法使用的是双轴快排。

💡

双轴快排 (DualPivotQuicksort) 的基本思想是：

顾名思义有两个轴元素 pivot1，pivot2，且 pivot ≤pivot2 将序列分成三段：x <pivot1、pivot1 ≤ x ≤ pivot2、x>pivot2 然后分别对三段进行递归

以下是其核心思想的详细阐述：

分治法

Arrays.sort() 采用了分治法的策略，即将大问题分解为小问题来解决。在排序过程中，它首先选择一个基准元素（pivot），然后将数组分为两部分：一部分包含所有小于基准元素的元素，另一部分包含所有大于基准元素的元素。接下来，递归地对这两部分进行相同的操作，直到整个数组有序。

多种排序算法结合

‌快速排序‌：对于基本数据类型（如int、short、long等），Arrays.sort() 主要采用快速排序算法。快速排序通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

‌归并排序‌：对于对象类型（如Integer、String等），Arrays.sort() 则采用归并排序算法。归并排序是一种稳定的排序算法，它通过合并两个已排序的序列来排序整个序列。归并排序的时间复杂度也是O(n log n)，但它是稳定的，且对于对象类型的数据，比较操作通常比移动操作更耗时，因此归并排序在这种情况下更为合适。

优化策略

‌小数组优化‌：当待排序的数组中的元素个数较少时（JDK源码中的阀值通常为7），Arrays.sort() 会采用插入排序算法。这是因为对于小数组，插入排序的时间复杂度虽然为O(n^2)，但由于其实现简单且不需要额外的递归调用或空间开销，因此在小数组上通常比快速排序或归并排序更高效。

‌基准元素选择‌：为了避免最坏情况的发生（即每次分区都极不平衡），Arrays.sort() 在选择基准元素时采用了多种策略。例如，当数组大小适中时（大于7且小于等于40），它会选择首、中、末三个元素中的中值作为基准元素；当数组较大时（大于40），它会从数组中较均匀地选择多个元素来确定一个伪中值作为基准元素。

‌稳定性处理‌：对于需要稳定性的场景（如对象类型排序），Arrays.sort() 通过使用归并排序来保证排序的稳定性。

图文内容来自深入理解Arrays.sort()底层实现-腾讯云

sort 方法进来后，调用了 DualPivotQuicksort.sort()。传统快排（单轴快排）的时间复杂度最差的情况为 n²，DualPivotQuicksort（双轴快排）能保证大多数数组排序的时间复杂度保持在 O(nlogn) 。

数组长度小于 286

DualPivotQuicksort.sort() 进来后，会碰到第一个阀值：QUICKSORT_THRESHOLD（286），数组长度小于这个阀值的进入插入排序或者 Quicksort （快速排序）

数组长度小于 47

进入 sort(a, left, right, true)，遇到们第二个阀值 INSERTION_SORT_THRESHOLD（47）。如果元素少于 47 这个阀值，就用插入排序。参数 leftmost 的含义是给定的范围，是不是这个数组最左边的部分。

数组长度大于等于 47

如果大于 47 这个阀值，则选择一种快速排序的方法：选出 e1,e2,e3,e4,e5 五个点，将数组等分为 6 份，称为 “基准”（pivot）；针对这个 5 个元素，进行插入排序。

选取 a[e2]，a[e4] 分别作为 pivot1，pivot2。由于进行了插入排序，pivot1 <=pivot2 。定义两个指针 less 和 great。less 从最左边开始向右遍历，一直找到第一个不小于 pivot1 的元素；great 从右边开始向左遍历，一直找到第一个不大于 pivot2 的元素。

指针 k 从 less-1 开始向右遍历至 great，把小于 pivot1 的元素移动到 less 左边，大于 pivot2 的元素移动到 great 右边。

将 less-1 处的元素移动到队头，great+1 处的元素移动到队尾，并把 pivot1 和 pivot2 分别放到 less-1 和 great+1 处。至此，less 左边的元素都小于 pivot1，great 右边的元素都大于 pivot2，分别对两部分进行同样的递归排序。

在这里其实有一个分支，如果 e1，e2，e3，e4，e5 有相等的情况，

则选取 a[e3] 作为 pivot，即经典的单轴快排。

数组长度大于等于 286

数组长度小于 286 的情况已经介绍完了，当大于等于 286 的时候先对数组进行一个Check if the array is nearly sorted判断，看看是否适合使用归并排序。这个判断主要作用是看数组具不具备有序结构：每降序为一个组，像 1,9,8,7,6,8。9 到 6 是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后最后的 8 后面继续往后面找。每遇到这样一个降序组，++count，当 count 大于 MAX_RUN_COUNT（67）或者有超过 33 个相同元素即 MAX_RUN_LENGTH（33），被判断为这个数组不具备有序结构，送给之前的 sort(int[] a, int left, int right, boolean leftmost)（The array is not highly structured,use Quicksort instead of merge sort）。反之进入归并排序。

TimeSort 排序

💡

Timsort 是一个混合、稳定的排序算法，简单来说就是归并排序和二分插入排序算法的混合体，号称世界上最好的排序算法。Timsort一直是 Python 的标准排序算法。Java SE 7 后添加了Timsort API ，我们从Arrays.sort可以看出它已经是非原始类型数组的默认排序算法了。所以不管是进阶编程学习还是面试，理解 Timsort 是比较重要。

理解 Timsort 需要先了解下面的知识

指数搜索

指数搜索，也被称为加倍搜索，是一种用于在大型数组中搜索元素而创建的算法。它是一个两步走的过程。首先，该算法试图找到目标元素存在的范围 (L，R)，然后在这个范围内使用二叉搜索来寻找目标的准确位置。时间复杂度为 O(lg⁡n)O(lgn)。该搜索算法在大量有序数组中比较有效。

二分插入排序

插入排序算法很简单，大体过程是从第二个元素开始，依次向前移动交换元素直到找到合适的位置。

插入排序最优时间复杂度也要 O(n)O(n) ，我们可以使用二分查找来减少插入时元素的比较次数，将时间复杂度降为 log⁡nlogn。但是注意，二分查找插入排序仍然需要移动相同数量的元素，但是复制数组的时间消耗低于逐一互换操作。
特点：二分插入排序主要优点是在小数据集场景下排序效率很高。

归并排序

💡

归并排序是利用分治策略的算法，包含两个主要的操作：分割与合并。大体过程是，通过递归将数组不断分成两半，一直到无法再分割（也就是数组为空或只剩一个元素），然后进行合并排序。简单来说合并操作就是不断取两个较小的排序数组然后将它们组合成一个更大的数组。

特点：归并排序主要为大数据集场景设计的排序算法。

Timsort 执行过程

💡

算法大体过程，如果数组长度小于指定阀值（MIN_MERGE）直接使用二分插入算法完成排序，否则执行下面步骤：

先从数组左边开始，执行升序运行得到一个子序列。

将这个子序列放入运行堆栈里，等待执行合并。

检查运行堆栈里的子序列，如果满足合并条件则执行合并。

重复第一个步骤，执行下一个升序运行。

升序运行

升序运行就是从数组查找一段连续递增（升序）或递减（降序）子序列的过程，如果子序列为降序则将它反转为升序，也可以将这个过程简称为 run。比如数组 [2,3,6,4,9,30]，可以查找到三个子序列，[2,3,6]、[4,9]、[30]，或说3个 run。

几个关键阀值

MIN_MERGE

这是个常数值，可以简单理解为执行归并的最小阀值，如果整个数组长度小于它，就没必要执行那么复杂的排序，直接二分插入就行了。在 Tim Peter 的 C 实现中为 64，但实际经验中设置为 32 效果更好，所以 java 里面此值为 32。

降序反转时为保证稳定性，相同元素不会被颠倒。

minrun

在合并序列的时候，如果 run 数量等于或者略小于 2 的幂次方的时候，合并效率最高；如果略大于 2 的幂次方，效率就会显著降低。所以为了提高合并效率，需要尽量控制每个 run 的长度，通过定义一个 minrun 来表示每个 run 的最小长度，如果长度太短，就用二分插入排序把 run 后面的元素插入到前面的 run 里面。

一般在执行排序算法之前，会先计算出这个 minrun（它是根据数据的特点来进行自我调整），minrun 会从32到64选择一个数字，因此数据的大小除以 minrun 等于或略小于 2 的幂次方。比如长度是 65 ，那么 minrun 的值就是 33；如果长度是 165，minrun 就是 42。

看下 Java 里面的实现，如果数据长度（n） < MIN_MERGE，则返回数据长度。如果数据长度恰好是 2 的幂次方，则返回MIN_MERGE/2

也就是16，否则返回一个MIN_MERGE/2 <= k <= MIN_MERGE范围的值k，这样可以使的 n/k 接近但严格小于 2 的幂次方。

MIN_GALLOP

MIN_GALLOP 是为了优化合并的过程设定的一个阈值，控制进入 GALLOP 模式中， GALLOP 模式放在后面讲。

下面是 Timsort 执行流程图

运行合并

当栈里面的 run 满足合并条件时，它就将栈里面相邻的两个run 进行合并。

合并条件

Timsort 为了执行平衡合并（让合并的 run 大小尽可能相同），制定了一个合并规则，对于在栈顶的三个run，分别用X、Y 和 Z 表示他们的长度，其中 X 在栈顶，它们必须始终维持一下的两个规则：

一旦有其中的一个条件不被满足，则将 Y 与 X 或 Z 中的较小者合并生成新的 run，并再次检查栈顶是否仍然满足条件。如果不满足则会继续进行合并，直至栈顶的三个元素都满足这两个条件，如果只剩两个run，则满足 Y > X 即可。

如下下图例子

当 Z <= Y+X ，将 X+Y 合并，此时只剩下两个run。

检测 Y < X ，执行合并，此时只剩下 X，则退出合并检测。

我们看下 Java 里面的合并实现

合并内存开销

原始归并排序空间复杂度是 O(n)O(n) 也就是数据大小。为了实现中间项，Timsort 进行了一次归并排序，时间开销和空间开销都比 O(n)O(n) 小。

优化是为了尽可能减少数据移动，占用更少的临时内存，先找出需要移动的元素，然后将较小序列复制到临时内存，在按最终顺序排序并填充到组合序列中。

比如我们需要合并 X [1, 2, 3, 6, 10] 和 Y [4, 5, 7, 9, 12, 14, 17]，X 中最大元素是10，我们可以通过二分查找确定，它需要插入到 Y 的第 5个位置才能保证顺序，而 Y 中最小元素是4，它需要插入到 X 中的第4个位置才能保证顺序，那么就知道了[1, 2, 3] 和 [12, 14, 17] 不需要移动，我们只需要移动 [6, 10] 和 [4, 5, 7, 9]，然后只需要分配一个大小为 2 临时存储就可以了。