算法解惑：快速排序(一) | VyronLee's Notebook

type

status

date

slug

summary

引言

快速排序（Quick Sort）是一种高效的排序算法，它采用分而治之的策略，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。本文将详细讲解快速排序的原理，并按照从基本快速排序到其不同变体的顺序，逐步展开讨论。

基本概念

快速排序的核心思想是选取一个基准值（pivot），然后将数组分为两部分，左边部分所有元素小于基准值，右边部分所有元素大于基准值（相同的数可以到任一边），这个过程称为一次分区（partition）。通过递归地对分区后的子数组进行同样的操作，直到数组完全有序。

算法解释

快速排序算法执行以下步骤：

选择基准值：通常选择第一个元素或最后一个元素作为基准。

分区操作：重新排列数组，使得比基准值小的所有元素都在基准前面，而所有比基准值大的元素都在基准后面。在这个分区退出之后，该基准就处于数组的最终位置。

递归排序：递归地将小于基准值的子数组和大于基准值的子数组排序。

代码框架

基本快速排序

基本快速排序，即：一路快速排序，它是快速排序最基本的形式。

步骤详解

选择基准元素：选择数组中的一个元素作为基准（pivot）。这里我们选择第一个元素。

分区操作：设置一个指针i来遍历数组，以及一个指针j来表示基准元素最终应该存放的位置。初始时，j指向数组的第一个位置。

遍历与交换：从数组的第二个元素开始遍历，对于每个元素arr[i]，执行以下操作：

如果arr[i] 小于基准元素pivot，则应该将其移动到基准元素的左边。为此，我们先将j加一（这样j指向的位置就是当前小于pivot的元素应该存放的位置），然后交换arr[i]和arr[j]。如果arr[i] 大于等于基准元素，则不需要做任何操作，继续遍历下一个元素。

遍历完所有元素后，将基准元素与arr[j]交换。此时，基准元素位于其最终位置，它左边的所有元素都不大于它，右边的所有元素都不小于它。

递归排序：将基准元素左侧和右侧的子数组分别进行单路快速排序。这两个子数组不包括基准元素。

递归结束条件：当子数组的大小缩减到1或0时，递归结束，因为单个元素或空数组自然是有序的。

组合：由于快速排序是就地排序，不需要额外的合并步骤，所有子数组在被递归排序后，整个数组将变得有序。

代码示例

过程说明

我们以上述代码中的数据 [23,4,41,8,65,34,8,22,7,84,14,8] 为例进行说明

第一次分区：low = 0, high = 11, pivot = 23 ，流程如下

第一次分区结果：[8,4,8,8,22,7,14,23,34,84,41,65] 其中 j = 7 为 pivot(23) 的最终位置

然后对左边区域 low = 0, high = 6 进行递归分区，依次得到结果（红底数字为基准值）：

[(7,4,8,8,22,8,14),23,34,84,41,65]

[(4,7),8,8,22,8,14,23,34,84,41,65]

[4,(7),8,8,22,8,14,23,34,84,41,65]

[4,7,8,(8,22,8,14),23,34,84,41,65]

[4,7,8,8,(14,8,22),23,34,84,41,65]

[4,7,8,8,(8,14),22,23,34,84,41,65]

[4,7,8,8,(8),14,22,23,34,84,41,65]

对右边区域 low = 7, high = 11 进行递归分区，依次得到结果：

[4,7,8,8,8,14,22,23,(34,84,41,65)]

[4,7,8,8,8,14,22,23,34,(65,41,84)]

[4,7,8,8,8,14,22,23,34,(41,65),84]

[4,7,8,8,8,14,22,23,34,(41),65,84]

得到最终排序结果：[4,7,8,8,8,14,22,23,34,41,65,84]

潜在的问题

基本快速排序的主要问题在于基准值的选择。如果每次分区时基准值都是最小或最大的元素，那么快速排序的时间复杂度会退化为O(n²)，特别是在处理已经有序或接近有序的数据时性能较差。

随机快速排序

基本概念

为了克服基本快速排序选择基准值可能导致的不平衡问题，随机快速排序在每次分区前随机选择一个元素作为基准值。这种策略可以提高算法在各种输入情况下的性能表现。

算法解释

随机快速排序的分区操作与基本快速排序相同，不同之处在于基准值的选择。在随机快速排序中，我们首先从子数组中随机选择一个元素与第一个元素交换，然后以这个交换后的第一个元素作为基准值进行分区。

代码示例

潜在的问题

虽然随机快速排序在平均情况下性能良好，但是在极端情况下仍然可能出现不平衡的分区，导致性能不稳定。

三数取中快速排序

基本概念

三数取中快速排序是对基准值选择策略的进一步优化。它从数组的首部、中部和尾部分别取出三个数，然后计算这三个数的中值，并以这个中值作为基准值进行分区。这种方法能够更有效地防止分区不平衡。

算法解释

在三数取中快速排序中，首先从数组的首部、中部和尾部取出三个数，然后通过比较和交换这三个数，找出它们的中值。将中值与第一个元素交换后，再按照基本快速排序的分区方法进行分区。

代码示例

潜在的问题

尽管三数取中快速排序在很多情况下都能避免最坏情况的发生，但是在一些特定的输入下，如包含大量重复元素的数组，它的性能仍然不是最优的。

下一篇章我们再来解决在含有大量重复元素时的优化问题。