Hoare 分区算法详解

给定一个数组 arr[]，我们的任务是以第一个元素作为枢轴来对数组进行分区。

数组的分区必须满足以下两个条件：

• 小于枢轴元素的元素必须出现在小于或等于分区索引的位置。
• 大于或等于枢轴元素的元素必须出现在大于分区索引的位置。

分区索引等于严格小于枢轴的元素个数减一。
注意：可能存在不止一种满足条件的分区结果。
示例：

> 输入： arr[] = [5, 3, 8, 4, 2, 7, 1, 10]

> 输出： [1, 3, 2, **4**, 8, 7, 5, 10]

> 解释： 分区索引为 3，枢轴元素是 5。所有小于枢轴的元素 [1, 3, 2, 4] 被安排在分区索引之前，而大于或等于枢轴的元素 [8, 7, 5, 10] 被安排在分区索引之后。

>

> 输入： arr[] = [12, 10, 9, 16, 19, 9]

> 输出： [9, 10, **9**, 16, 19, 12]

> 解释： 分区索引为 2，枢轴元素是 12。所有小于枢轴的元素 [9, 10, 9] 被安排在分区索引处或之前，而大于或等于枢轴的元素 [16, 19, 12] 被安排在分区索引之后。

目录

• Hoare 数组分区算法
• 一些有趣的事实

Hoare 数组分区算法

> Hoare 分区算法是一种围绕枢轴对数组进行分区的有效方法。它基于双指针技术，这两个指针从数组的两端开始并向彼此移动，直到找到需要交换的元素。

让我们逐步解析这个算法：

• 将第一个元素视为枢轴，并初始化两个指针，INLINECODE3df1cd49 在数组开头，INLINECODEa6052049 在数组末尾。
• 向右移动 INLINECODE77f9b674 直到找到大于或等于枢轴的元素，向左移动 INLINECODE0037498f 直到找到小于或等于枢轴的元素。
• 如果 INLINECODE3a8b46cb 指向的元素大于或等于枢轴，且 INLINECODE236e25ad 指向的元素小于或等于枢轴，则交换它们。
• 重复此过程，不断移动 INLINECODEd7e04682 和 INLINECODEa2658d60 使它们彼此靠近，直到它们相遇或交叉。
• 当指针交叉时，分区完成，左边是小于或等于枢轴的元素，右边是大于或等于枢轴的元素。

C++


CODEBLOCK_00509231


C


CODEBLOCK_ad238a4b


Java


CODEBLOCK_cd22f5bc


Python


CODEBLOCK_68c448fd


C#


CODEBLOCK_1341318b


JavaScript


CODEBLOCK_45303cfb


一些有趣的事实

• 比 Lomuto 分区更高效：Hoare 分区通常比 Lomuto 分区方案快 3 倍，因为它平均进行的交换次数更少。Lomuto 分区会对每个小于枢轴的元素进行交换，而 Hoare 分区只在必要时交换（当左侧元素大于枢轴且右侧元素小于枢轴时）。

• 指针移动方式：在 Hoare 的方案中，两个指针从两端向中间移动，而 Lomuto 方案只使用一个从左到右移动的指针。

• 枢轴的最终位置：与 Lomuto 分区不同（枢轴保证被放置在其最终排序位置），Hoare 分区不将枢轴元素放置在其正确的排序位置。当指针交叉时，枢轴元素可能与某些其他元素交换。不过，这并不影响快速排序的正确性，因为我们只是确保了数组已经被分为两个部分，然后递归处理即可。

• 处理重复元素：Hoare 分区算法能更高效地处理数组中存在大量重复元素的情况，因为它会跳过相等的元素，减少了不必要的交换。