算法专题七：分治

快排

1.颜色分类

题目链接：75. 颜色分类 - 力扣（LeetCode）

class Solution {public void swap(int[] nums, int i, int j){int t = nums[i];nums[i] = nums[j];nums[j] = t;}public void sortColors(int[] nums) {int left=-1 ,i=0 ,right=nums.length;while(i<right){if(nums[i] == 0) swap(nums, ++left, i++);else if(nums[i] == 1) i++;else swap(nums, --right, i);}}
}

2.排序数组

题目链接：912. 排序数组 - 力扣（LeetCode） 

排序的规则和颜色分类的思想基本一致

那么key的值如何选择 

class Solution {public int[] sortArray(int[] nums) {int left=0;int right=nums.length-1;qsort(nums,left,right);return nums;}public void qsort(int[] nums,int l,int r){if(l>=r){return;}int key=nums[new Random().nextInt(r-l+1)+l];int left=l-1;int right=r+1;int i=l;while(i<right){if(nums[i]<key){swap(nums,++left,i++);}else if(nums[i]==key){i++;}else{swap(nums,--right,i);}}qsort(nums,l,left);qsort(nums,right,r);}public void swap(int[] nums,int m,int n){int t=nums[m];nums[m]=nums[n];nums[n]=t;}
}

3.数组中第k个最大元素

题目链接：215. 数组中的第K个最大元素 - 力扣（LeetCode）