快速排序的分区优化：三路划分（Three-way Partitioning） 一、问题描述 快速排序的核心步骤是分区（partition），即将数组划分为两个部分，使得左半部分的元素都小于等于基准值（pivot），右半部分的元素都大于等于基准值。传统分区（如Lomuto分区或Hoare分区）在处理大量重复元素时效率较低，因为重复元素会导致分区不平衡。三路划分（Three-way Partitioning）是快速排序的一种优化，专门用于处理包含大量重复元素的数组。它通过一次扫描将数组划分为三个区域：小于pivot的元素、等于pivot的元素、大于pivot的元素，从而提高排序效率，尤其适用于有大量重复键值的情况。 二、背景与动机 在传统快速排序中，如果数组中存在大量重复元素，分区后等于pivot的元素可能会集中在某一侧，导致递归树不平衡，最坏情况下时间复杂度退化到O(n²)。三路划分通过将等于pivot的元素集中在中间，避免在后续递归中对它们重复排序，从而优化性能。它在实际应用中很常见，例如在排序整数或字符串时，重复元素是常有的。 三、算法步骤详解 三路划分算法的核心是维护三个指针： low 、 mid 、 high ，将数组划分为四个区域，初始时 low 和 mid 指向数组起始， high 指向数组末尾。然后遍历数组，根据当前元素与pivot的比较结果，交换元素并移动指针。以下是具体步骤： 选择基准值（pivot） ：通常选择数组的第一个元素、最后一个元素或随机元素作为pivot。这里以数组的第一个元素为例，pivot = arr[ left ]。 初始化指针 ： low 指针：指向小于pivot区域的末尾（即从数组左端开始，所有小于pivot的元素都放在 low 左侧）。 mid 指针：当前遍历的指针，从数组左端开始向右移动。 high 指针：指向大于pivot区域的起始（即从数组右端开始，所有大于pivot的元素都放在 high 右侧）。 初始时， low = left ， mid = left ， high = right （假设数组索引从 left 到 right ）。 遍历与分区 ： 使用 mid 指针遍历数组，直到 mid 超过 high 指针。在每一步中，根据 arr[mid] 与pivot的比较结果进行如下操作： 如果 arr[mid] < pivot ：交换 arr[low] 和 arr[mid] ，然后 low 和 mid 都向右移动一位。这是因为小于pivot的元素应该放在左侧区域。 如果 arr[mid] == pivot ： mid 向右移动一位，而不做交换。这是因为等于pivot的元素保留在中间区域。 如果 arr[mid] > pivot ：交换 arr[mid] 和 arr[high] ，然后 high 向左移动一位，但 mid 不动。这是因为大于pivot的元素放在右侧区域，交换后 arr[mid] 是新元素，需要重新比较。 递归排序 ： 分区完成后，数组被划分为三个部分： 左部分：索引从 left 到 low-1 ，所有元素小于pivot。 中间部分：索引从 low 到 high ，所有元素等于pivot。 右部分：索引从 high+1 到 right ，所有元素大于pivot。 然后，递归地对左部分和右部分进行快速排序（中间部分已有序，无需再排序）。 终止条件 ： 当左部分或右部分的大小为0或1时，递归终止。 四、举例说明 假设数组 arr = [3, 1, 2, 3, 4, 2, 3] ，pivot选择为第一个元素3，分区过程如下： 初始： low = 0 , mid = 0 , high = 6 , pivot = 3。 步骤1： arr[mid] = 3 ，等于pivot， mid 右移 → mid=1 。 步骤2： arr[mid] = 1 ，小于pivot，交换 arr[low] 和 arr[mid] （交换3和1）， low 和 mid 右移 → 数组变为 [1, 3, 2, 3, 4, 2, 3] , low=1 , mid=2 。 步骤3： arr[mid] = 2 ，小于pivot，交换 arr[low] 和 arr[mid] （交换3和2）， low 和 mid 右移 → 数组变为 [1, 2, 3, 3, 4, 2, 3] , low=2 , mid=3 。 步骤4： arr[mid] = 3 ，等于pivot， mid 右移 → mid=4 。 步骤5： arr[mid] = 4 ，大于pivot，交换 arr[mid] 和 arr[high] （交换4和3）， high 左移 → 数组变为 [1, 2, 3, 3, 3, 2, 4] , high=5 , mid 仍为4。 步骤6： arr[mid] = 3 ，等于pivot， mid 右移 → mid=5 。 步骤7： arr[mid] = 2 ，小于pivot，交换 arr[low] 和 arr[mid] （交换3和2）， low 和 mid 右移 → 数组变为 [1, 2, 2, 3, 3, 3, 4] , low=3 , mid=6 。 此时 mid > high ，遍历结束。最终数组划分为： 左部分：索引0-2，元素 [1, 2, 2] （小于3）。 中间部分：索引3-5，元素 [3, 3, 3] （等于3）。 右部分：索引6，元素 [4] （大于3）。 递归排序左部分和右部分即可。 五、时间复杂度与空间复杂度 时间复杂度：平均情况下为O(n log n)，最坏情况下（当所有元素都相等时）为O(n)，因为三路划分能避免递归重复元素，只需一次遍历。相比传统快速排序的最坏O(n²)，性能大幅提升。 空间复杂度：平均情况下为O(log n)用于递归栈，最坏情况下为O(n)（如果递归不平衡）。 六、应用与扩展 三路划分优化是快速排序在实践中的重要改进，特别适用于有大量重复数据的场景，例如排序日志文件、数据库查询结果等。它也被应用于一些标准库中，如Java的 Arrays.sort() 在排序对象数组时使用了类似技术。此外，三路划分的思想还可扩展到“荷兰国旗问题”（Dutch National Flag Problem），用于分类三种颜色的元素。