## 快速排序優化版 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; } } ~~~