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 实现代码

1. public class ThreeWayQuickSort {
3.     public static void sort(int[] arr) {
4.         if (arr == null || arr.length <= 1) return;
5.         threeWayQuickSort(arr, 0, arr.length - 1);
6.     }
8.     private static void threeWayQuickSort(int[] arr, int low, int high) {
9.         if (low >= high) return;
11.         // 选择基准值（这里选第一个元素）
12.         int pivot = arr[low];
13.         int lt = low;      // 小于 pivot 的右边界
14.         int gt = high;     // 大于 pivot 的左边界
15.         int current = low; // 当前遍历指针
17.         while (current <= gt) {
18.             if (arr[current] < pivot) {
19.                 swap(arr, lt, current);
20.                 lt++;
21.                 current++;
22.             } else if (arr[current] > pivot) {
23.                 swap(arr, current, gt);
24.                 gt--;
25.             } else {
26.                 current++;
27.             }
28.         }
30.         // 递归处理小于和大于区域
31.         threeWayQuickSort(arr, low, lt - 1);
32.         threeWayQuickSort(arr, gt + 1, high);
33.     }
35.     private static void swap(int[] arr, int i, int j) {
36.         int temp = arr[i];
37.         arr[i] = arr[j];
38.         arr[j] = temp;
39.     }
41.     public static void main(String[] args) {
42.         int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
43.         sort(arr);
44.         System.out.println(Arrays.toString(arr));
45.         // 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
46.     }
47. }

复制代码

关键步调解析

• 初始化指针：
  
  
  
  • 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]。
  

---

上风与适用场景

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。