## 快速排序 QuickSort * 空間復雜度：O(nLogN) * 時間復雜度：O(nLogN) ## 思路描述 1. 先選擇一個基準點p，以基準點p做分區操作（將比p小的數放到p的左邊，比p大的數放到右邊） 2. 然后遞歸在左邊0到p-1的部分排序，sort(0,p-1) 3. 再遞歸排右邊部分sort(p+1,len) 4. 如果left>=right,則退出 如下圖：  ## 例子 ``` old:[13, 7, 4, 6, 9, 24] partition: old=[13, 7, 4, 6, 9, 24] partition: left=0,right=5,value=4,j=0,swapCount=2 [4, 7, 13, 6, 9, 24] partition: old=[7, 13, 6, 9, 24] partition: left=1,right=5,value=6,j=1,swapCount=2 [6, 13, 7, 9, 24] partition: old=[13, 7, 9, 24] partition: left=2,right=5,value=7,j=2,swapCount=2 [7, 13, 9, 24] partition: old=[4, 6] partition: left=0,right=1,value=4,j=0,swapCount=2 [4, 6] partition: old=[13, 9, 24] partition: left=3,right=5,value=9,j=3,swapCount=2 [9, 13, 24] partition: old=[4, 6, 7] partition: left=0,right=2,value=6,j=1,swapCount=3 [4, 6, 7] partition: old=[13, 24] partition: left=4,right=5,value=13,j=4,swapCount=2 [13, 24] partition: old=[4, 6, 7, 9] partition: left=0,right=3,value=6,j=1,swapCount=3 [4, 6, 7, 9] partition: old=[7, 9] partition: left=2,right=3,value=7,j=2,swapCount=2 [7, 9] partition: old=[4, 6] partition: left=0,right=1,value=4,j=0,swapCount=2 [4, 6] result:[4, 6, 7, 9, 13, 24]耗時:5ms ``` ## java實現 ~~~ public class QuickSort { public static void main(String[] args) { Stopwatch sw = Stopwatch.createStarted(); int[] nums = {13,7,4,6,9,24}; 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,0,p-1); // 遞歸排右邊的 quickSort(nums,p+1,right); } // 對arr[l...r]部分進行partition操作 // 返回index, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] private static int partition(int[] nums, int left, int right) { // 基準值 int[] newNums = Arrays.copyOfRange(nums,left,right+1); int p = (left + right) / 2; // 將基準值和left交換 int swapCount = 2; swap(nums, left, p); int value = nums[left]; int j = left; for (int i = left + 1; i <= right; i++){ if (nums[i] < value) { j++; swap(nums, j, i); swapCount ++; } } swap(nums, left, j); System.out.println("partition: old="+Arrays.toString(newNums)); int[] sortNums = Arrays.copyOfRange(nums,left,right+1); System.out.println("partition: left="+left+",right="+right+",value=" + value + ",j=" + j + ",swapCount=" + swapCount + " " + Arrays.toString(sortNums)); return j; } // 交換數組下標 public static void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } ~~~