深入解析三路快速排序：一种高效的排序算法

深入解析三路快速排序：一种高效的排序算法

引用

CSDN

1.

https://blog.csdn.net/qq_41591215/article/details/141183153

在数据结构和算法的世界中，快速排序（Quick Sort）无疑是应用最广泛的排序算法之一。本文将深入探讨快速排序的一种优化变体——三路快速排序（3-Way Quick Sort），它在处理包含大量重复元素的数组时展现出显著的效率优势。

1. 快速排序的基本概念

在深入探讨三路快速排序之前，我们先回顾一下经典的快速排序算法。快速排序由C.A.R. Hoare于1960年提出，采用分治策略，通过选择一个基准元素（pivot），将数组分为两部分：一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素，然后递归地对这两部分进行排序。

快速排序的基本步骤如下：

• 选择基准元素：通常选择数组的第一个、最后一个或中间的元素作为基准。
• 分区操作：将数组分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
• 递归排序：对分出的两部分分别递归地应用快速排序。

2. 三路快速排序的动机与改进

在经典的快速排序中，当遇到大量重复元素时，分区操作会变得非常低效，导致性能下降。三路快速排序则通过对重复元素进行特殊处理来解决这个问题。

为什么需要三路快速排序？

在处理大量重复元素的数组时，经典的快速排序可能会表现得非常低效，因为重复元素会导致很多不必要的比较和交换。三路快速排序通过将数组分为三个区域来优化这一点：

• 小于基准元素的区域
• 等于基准元素的区域
• 大于基准元素的区域

这种分区方法减少了重复元素的处理次数，提高了效率。如图：

三路快速排序的步骤

1. 选择基准元素：选择一个基准元素（随机选取，并与第一个元素交换）。
2. 分区操作：使用三个指针（lt, i, gt）来划分数组：

• lt指向小于基准的区域的边界
• i是当前元素的索引
• gt指向大于基准的区域的边界

3. 交换元素：

• 如果当前元素小于基准，将其移动到小于区域，更新lt和i。
• 如果当前元素等于基准，将其保持在中间区域，更新i。
• 如果当前元素大于基准，将其移动到大于区域，更新gt。

举例说明

原始数组如下：

步骤1: 假设随机选取的下标是3，将它与第一个元素交换位置，交换后原数组不变

步骤二：初始化三个指针
步骤三：交换元素
2比基准值5小，交换位置swap(i,lt)，然后lt，i分别向右移动
3比基准值5小，交换位置swap(i,lt)，然后lt，i分别向右移动

5和基准值5相等，向右移动i

7比基准值5大，交换位置swap(i,gt)，gt向左移动

8比基准值5大，交换位置swap(i,gt)，gt向左移动
至此，我们把比基准值小的数放在索引小于lt的位置，比基准值大的放在索引>gt的位置上，[lt, gt]是等于基准值的

3. 代码实现

/**
 * 三路快速排序
 * 三路快速排序是快速排序的一种优化，它将数组分为三个部分：
 * 小于基准值的元素、等于基准值的元素和大于基准值的元素。
 * 这样可以减少递归深度，提高排序效率。
 * 
 * @param arr 待排序的数组
 * @param low 子区间的起始索引
 * @param high 子区间的结束索引
 */
public void threeWayQuickSort(int[] arr, int low, int high) {
    // 当起始索引大于等于结束索引时，无需排序，直接返回
    if (low >= high) {
        return;
    }
    // 随机选择一个索引作为基准值的索引
    int v = (int)(Math.random() * (high - low + 1) + low);
    // 将基准值交换到区间起始位置
    swap(arr, low, v);
    // 获取基准值
    int pivot = arr[low];
    // 初始化小于基准值的边界
    int lt = low;
    // 初始化当前比较位置
    int i = low + 1;
    // 初始化大于基准值的边界
    int gt = high;
    // 遍历数组，直到当前比较位置与大于基准值的边界相遇
    while (i <= gt) {
        if (arr[i] < pivot) {
            // 当前元素小于基准值，将其与小于边界后的元素交换，并移动小于边界和当前比较位置
            swap(arr, lt, i);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            // 当前元素大于基准值，将其与大于边界的元素交换，并移动大于边界
            swap(arr, i, gt);
            gt--;
        } else {
            // 当前元素等于基准值，直接移动到下一个位置
            i++;
        }
    }
    // 递归地对小于基准值的部分和大于基准值的部分进行排序
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

4. 性能分析

时间复杂度

在最坏情况下（例如所有元素相等），三路快速排序的时间复杂度仍然是O(n log n)，与经典的快速排序相同。但在处理重复元素时，它通常比经典快速排序更具优势。

空间复杂度

三路快速排序的空间复杂度为O(log n)，因为它使用了递归栈来进行排序。