Java-三路快排

2025-03-07 约 807 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146094071

Java 三路快排

三路快速排序（ 3-Way QuickSort ）是快速排序的优化版本，特别适用于 处理包含大量重复元素的数组 。其核心思想是将数组划分为三个区域： 小于基准值 、 等于基准值 和 大于基准值 ，从而减少不必要的递归和交换

三路快排原理

分区逻辑 ：
- 使用三个指针 lt （less than）、 current （当前遍历位置）、 gt （greater than）将数组划分为三部分：
  - [low, lt-1] ：小于基准值的元素
  - [lt, gt] ：等于基准值的元素
  - [gt+1, high] ：大于基准值的元素
- 通过一次遍历，将元素分配到正确区域。
时间复杂度 ：
- 平均： O(n log n)
- 最坏（大量重复元素时）： O(n) （优于传统快排的 O(n²) ）

Java 实现代码

public class ThreeWayQuickSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        threeWayQuickSort(arr, 0, arr.length - 1);
    }

    private static void threeWayQuickSort(int[] arr, int low, int high) {
        if (low >= high) return;

        // 选择基准值（这里选第一个元素）
        int pivot = arr[low];
        int lt = low;      // 小于 pivot 的右边界
        int gt = high;     // 大于 pivot 的左边界
        int current = low; // 当前遍历指针

        while (current <= gt) {
            if (arr[current] < pivot) {
                swap(arr, lt, current);
                lt++;
                current++;
            } else if (arr[current] > pivot) {
                swap(arr, current, gt);
                gt--;
            } else {
                current++;
            }
        }

        // 递归处理小于和大于区域
        threeWayQuickSort(arr, low, lt - 1);
        threeWayQuickSort(arr, gt + 1, high);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr)); 
        // 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
    }
}

关键步骤解析

初始化指针 ：
- lt 指向数组起始位置（ low ）， gt 指向数组末尾（ high ）， current 从 low 开始遍历。
遍历与交换 ：
- 如果 arr[current] < pivot ：将 current 与 lt 处的元素交换， lt 和 current 均右移。
- 如果 arr[current] > pivot ：将 current 与 gt 处的元素交换， gt 左移（ current 不移动，因为交换后的新元素需要再次检查）。
- 如果 arr[current] == pivot ：直接移动 current 指针。
递归处理子数组 ：
- 对 [low, lt-1] （小于区域）和 [gt+1, high] （大于区域）递归排序，中间区域 [lt, gt] 已经有序。

示例流程

假设初始数组为 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] ，基准值 pivot=3 ：

第一次分区后 ：
- 小于区域： [1, 1, 2]
- 等于区域： [3, 3]
- 大于区域： [4, 5, 9, 6, 5, 5]
递归排序小于区域 [1, 1, 2] 和大于区域 [4, 5, 9, 6, 5, 5] 。

优势与适用场景

优势：
- 高效处理重复元素，避免传统快排的重复递归。
- 减少元素交换次数。
适用场景 ：
- 数组中存在大量重复元素（如日志数据、用户行为数据）。
- 需要稳定排序但允许非稳定实现的情况。