快速排序（Quick Sort）

一、快速排序算法原理

快速排序（Quick Sort）是一种分治算法，核心思想是：

1. 选择基准值（Pivot）
2. 分区（Partition）：将数组分为两部分，左边都小于基准，右边都大于基准
3. 递归排序左右两部分

初始数组: [64, 34, 25, 12, 22, 11, 90] 选择 pivot = 22 (通常选最右或中间) 分区过程: [11, 12] [22] [64, 34, 25, 90] <22 pivot >22 递归排序左右...

1、基础实现（Hoare分区）

publicclassQuickSort{// 主排序方法publicstaticvoidquickSort(int[]arr,intlow,inthigh){if(low<high){// 获取分区点intpivotIndex=partition(arr,low,high);// 递归排序左半部分quickSort(arr,low,pivotIndex-1);// 递归排序右半部分quickSort(arr,pivotIndex+1,high);}}// Lomuto分区方案（简单直观）privatestaticintpartition(int[]arr,intlow,inthigh){intpivot=arr[high];// 选择最后一个元素作为基准inti=low-1;// i指向小于pivot的最后一个位置for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(arr,i,j);}}// 将pivot放到正确位置swap(arr,i+1,high);returni+1;}privatestaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}// 测试publicstaticvoidmain(String[]args){int[]arr={64,34,25,12,22,11,90};System.out.println("排序前: "+Arrays.toString(arr));quickSort(arr,0,arr.length-1);System.out.println("排序后: "+Arrays.toString(arr));}}

2、优化版本：三数取中 + 尾递归优化

publicclassQuickSortOptimized{// 插入排序阈值（小数组用插入排序更快）privatestaticfinalintINSERTION_THRESHOLD=10;publicstaticvoidquickSort(int[]arr,intlow,inthigh){// 小数组用插入排序if(high-low+1<=INSERTION_THRESHOLD){insertionSort(arr,low,high);return;}// 尾递归优化：先处理较小的子数组while(low<high){intpivotIndex=partition(arr,low,high);// 递归处理较小的部分，迭代处理较大的部分if(pivotIndex-low<high-pivotIndex){quickSort(arr,low,pivotIndex-1);low=pivotIndex+1;// 迭代处理右半部分}else{quickSort(arr,pivotIndex+1,high);high=pivotIndex-1;// 迭代处理左半部分}}}// 三数取中法选择pivotprivatestaticintmedianOfThree(int[]arr,intlow,inthigh){intmid=low+(high-low)/2;// 排序这三个数if(arr[low]>arr[mid])swap(arr,low,mid);if(arr[low]>arr[high])swap(arr,low,high);if(arr[mid]>arr[high])swap(arr,mid,high);// 将中位数放到倒数第二个位置swap(arr,mid,high-1);returnarr[high-1];}// Hoare分区（更高效，交换次数少）privatestaticintpartition(int[]arr,intlow,inthigh){intpivot=medianOfThree(arr,low,high);inti=low;intj=high-1;while(true){while(arr[++i]<pivot){}// 从左找 >= pivotwhile(arr[--j]>pivot){}// 从右找 <= pivotif(i>=j)break;swap(arr,i,j);}swap(arr,i,high-1);// 将pivot放到正确位置returni;}privatestaticvoidinsertionSort(int[]arr,intlow,inthigh){for(inti=low+1;i<=high;i++){intkey=arr[i];intj=i-1;while(j>=low&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;}}privatestaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}

3、双路快排（处理大量重复元素）

publicclassQuickSortDualPivot{// 双路快排：将等于pivot的元素均匀分布到两边publicstaticvoidquickSort2Way(int[]arr,intlow,inthigh){if(low>=high)return;intpivot=arr[low+(high-low)/2];inti=low,j=high;while(i<=j){while(arr[i]<pivot)i++;while(arr[j]>pivot)j--;if(i<=j){swap(arr,i++,j--);}}quickSort2Way(arr,low,j);quickSort2Way(arr,i,high);}// 三路快排（荷兰国旗问题，大量重复元素时O(n)）publicstaticvoidquickSort3Way(int[]arr,intlow,inthigh){if(low>=high)return;intpivot=arr[low];intlt=low;// arr[low..lt-1] < pivotintgt=high;// arr[gt+1..high] > pivotinti=low+1;// arr[lt..i-1] == pivotwhile(i<=gt){if(arr[i]<pivot){swap(arr,i++,lt++);}elseif(arr[i]>pivot){swap(arr,i,gt--);}else{i++;}}// 现在: [low,lt-1] < pivot, [lt,gt] == pivot, [gt+1,high] > pivotquickSort3Way(arr,low,lt-1);quickSort3Way(arr,gt+1,high);}privatestaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}

二、 算法可视化图解

初始: [5, 2, 9, 1, 5, 6, 3, 5] 选择 pivot = 5 (中间) 三路分区过程: i gt [5, 2, 9, 1, 5, 6, 3, 5] lt=0, i=1, gt=7 ^ ^ lt pivot在lt位置 Step 1: arr[i]=2 < 5, swap(i,lt), i++, lt++ [2, 5, 9, 1, 5, 6, 3, 5] lt=1, i=2 Step 2: arr[i]=9 > 5, swap(i,gt), gt-- [2, 5, 5, 1, 5, 6, 3, 9] i=2, gt=6 Step 3: arr[i]=5 == 5, i++ [2, 5, 5, 1, 5, 6, 3, 9] i=3 Step 4: arr[i]=1 < 5, swap(i,lt), i++, lt++ [2, 1, 5, 5, 5, 6, 3, 9] lt=2, i=4 Step 5: arr[i]=5 == 5, i++ [2, 1, 5, 5, 5, 6, 3, 9] i=5 Step 6: arr[i]=6 > 5, swap(i,gt), gt-- [2, 1, 5, 5, 5, 3, 6, 9] i=5, gt=5 Step 7: arr[i]=3 < 5, swap(i,lt), i++, lt++ [2, 1, 3, 5, 5, 5, 6, 9] lt=3, i=6 > gt=5 结束 结果: [<5: 2,1,3] [=5: 5,5,5] [>5: 6,9]

三、复杂度分析

四、使用建议

1. 基础版本：数据随机分布，学习理解用
2. 优化版本：生产环境，大数据量
3. 双路快排：数据中有部分重复元素
4. 三路快排：大量重复元素（如性别、状态字段）