【手撕】快排-分治
1. 颜色分类
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/sort-colors/description/
代码
class Solution {public void sortColors(int[] nums) {int left = -1 , right = nums.length;int i = 0;while( i < right){if(nums[i] == 0){swap(nums,++left , i++);}else if( nums[i] == 1){i++;}else{swap(nums,--right ,i);}}}private static void swap(int[] arr , int left , int right){int tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;}
}2. 快排
. - 力扣（LeetCode）
代码
class Solution {public int[] sortArray(int[] nums) {qsort(nums,0 , nums.length -1);return nums;}private static void qsort(int[] arr, int l , int r){if(l >= r) return ;int left = l - 1 , right = r + 1;//随机选择一个基准元素int povit = arr[new Random().nextInt( r - l + 1) + l];int i = l;//按照基准元素将数组划分成3块while( i < right){if(arr[i] < povit) swap(arr , ++left , i++);else if(arr[i] == povit) i++;else swap(arr , --right , i);}//继续划分qsort(arr, l , left);qsort(arr , right , r);}private static void swap(int[] arr , int a , int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
}3. 第 K 大
代码
class Solution {public int findKthLargest(int[] nums, int k) {return quickselect(nums, 0, nums.length - 1, k);}public static int quickselect(int[] nums, int l, int r, int k) {if( l == r) return nums[l];int povit = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1 , right = r + 1 , i = l;int a = 0 , b = 0, c = 0;while(i < right){if(nums[i] < povit) {swap(nums , ++left , i++);a++;}else if(nums[i] == povit){i++;b++;}else{swap(nums , --right , i);c++;}}//划分后根据数量决定继续去哪里找TOP Kif(c >= k) return quickselect(nums , right , r, k) ;else if(b+c >= k) return povit;else return quickselect(nums, l , left, k - b -c) ;}public static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}4. 返回最小的 K 个数
. - 力扣（LeetCode）
class Solution {public int[] inventoryManagement(int[] nums, int k) {qsort(nums, 0 , nums.length - 1, k);int[] ret = new int[k];for(int i = 0 ; i < k; i++){ret[i] = nums[i];}return ret;}private static void qsort(int[] nums, int l, int r, int k){while(l >= r) return;int povit = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;int a , b ,c ; a = 0; b= 0; c = 0;while(i < right){if(nums[i] < povit) {swap(nums, ++left , i++); a++;}else if(nums[i] == povit){ i++; b++;}else{ swap(nums, --right , i); c++;}}//划分完毕 根据情况决定去哪一部分继续寻找if(a >= k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}private static void swap(int[] nums, int a, int b){int tmp = nums[a];nums[a] = nums[b];nums[b] = tmp;}
}