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