## 快速排序优化版 QuickSort * 空间复杂度：O(nLogN) * 时间复杂度：O(nLogN) ## 思路描述 基于荷兰国旗问题做相关优化：[荷兰国旗问题](%E8%8D%B7%E5%85%B0%E5%9B%BD%E6%97%97%E9%97%AE%E9%A2%98.md) 1. 先选择一个基准点p，以基准点p做分区操作（将比p小的数放到p的左边，等于p的放中间，比p大的数放到右边） 2. 然后递归在左边0到小于p的index-1的部分排序，sort(0,p[0]-1) 3. 再递归排右边大于p的index+1的部分排序，sort(p[1]+1,len) 4. 如果left>=right,则退出 ## 例子 ``` * old:[13, 7, 4, 6, 4, 24, 4] * num=4 -> [4, 4, 4, 6, 24, 13, 7] * num=7 -> [4, 4, 4, 6, 7, 13, 24] * result:[4, 4, 4, 6, 7, 13, 24]耗时:9ms ``` ## java实现 ~~~ public class QuickFastSort { public static void main(String[] args) { Stopwatch sw = Stopwatch.createStarted(); int[] nums = {13,7,4,6,4,24,4}; System.out.println("old:"+ Arrays.toString(nums)); System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms"); } public static int[] sort(int[] nums){ quickSort(nums,0,nums.length-1); return nums; } // 快速排序 public static void quickSort(int[] nums,int left,int right){ if(left >= right){ return ; } // 基准坐标，分区 int[] p = partition(nums,left,right); // 递归排左边的 quickSort(nums,left,p[0]-1); // 递归排右边的 quickSort(nums,p[1]+1,right); } // 对arr[l...r]部分进行partition操作 // 荷兰国旗问题分区 private static int[] partition(int[] nums, int left, int right) { // 基准值，选中间值，也可以随机选 int p = (left + right) / 2; // 将基准值和right交换 swap(nums,p,right); // lt表示小于区域,i是遍历指针,gt表示大于区域 int lt = left-1; int gt = right; int i = left; int num = nums[p]; while (i < gt){ if(nums[i] < num){ // 小于当前数的，交换指针位置和小于区域下一个位置，小于区域和指针右移 swap(nums,++lt,i++); }else if(nums[i] == num){ i++; // 等于num，指针右移 }else{ // 大于当前数的，指针和大于区域前一位交换，大于区域左移 swap(nums,--gt,i); } } // 将基准值放回到gt位置 swap(nums,gt,right); System.out.println("num="+num + " -> " + Arrays.toString(nums)); return new int[]{lt+1,gt}; } // 交换数组下标 public static void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } ~~~