网络运维工程师自我介绍_网页设计作品展示模板_百度信息流推广_网站分析报告范文

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

三路快排原理

1. 分区逻辑：

   • 使用三个指针 lt（less than）、current（当前遍历位置）、gt（greater than）将数组划分为三部分：

     • [low, lt-1]：小于基准值的元素

     • [lt, gt]：等于基准值的元素

     • [gt+1, high]：大于基准值的元素

   • 通过一次遍历，将元素分配到正确区域。

2. 时间复杂度：

   • 平均：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]}
}

关键步骤解析

1. 初始化指针：

   • lt 指向数组起始位置（low），gt 指向数组末尾（high），current 从 low 开始遍历。

2. 遍历与交换：

   • 如果 arr[current] < pivot：将 current 与 lt 处的元素交换，lt 和 current 均右移。

   • 如果 arr[current] > pivot：将 current 与 gt 处的元素交换，gt 左移（current 不移动，因为交换后的新元素需要再次检查）。

   • 如果 arr[current] == pivot：直接移动 current 指针。

3. 递归处理子数组：

   • 对 [low, lt-1]（小于区域）和 [gt+1, high]（大于区域）递归排序，中间区域 [lt, gt] 已经有序。

---

示例流程

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

1. 第一次分区后：

   • 小于区域：[1, 1, 2]

   • 等于区域：[3, 3]

   • 大于区域：[4, 5, 9, 6, 5, 5]

2. 递归排序小于区域 [1, 1, 2] 和大于区域 [4, 5, 9, 6, 5, 5]。

---

优势与适用场景

• 优势：

  • 高效处理重复元素，避免传统快排的重复递归。

  • 减少元素交换次数。

• 适用场景：

  • 数组中存在大量重复元素（如日志数据、用户行为数据）。

  • 需要稳定排序但允许非稳定实现的情况。