优选算法的妙思之流：分治——快排专题

专栏：算法的魔法世界

个人主页：手握风云

目录

一、快速排序

二、例题讲解

2.1. 颜色分类

2.2. 排序数组

2.3. 数组中的第K个最大元素

2.4. 库存管理 III

---

一、快速排序

        分治，简单理解为“分而治之”，将一个大问题划分为若干个子问题，直到这个子问题能够快速解决。我们之前的快速排序是选出一个数作为基准值，然后将一个数组划分为两个子序列，一个序列<=基准值，另一个>基准值。但这种算法在数据特别大的时候是会超时的。所以我们这里要使用更优秀的三块划分和随机选择基准元素的算法。

二、例题讲解

2.1. 颜色分类

        这道题我们可以参照移动零里面的划分策略。移动零里面是利用双指针将数组分为0区域和非0区域，这道题我们也可以使用三个指针left、right、i来将其划分为0、1、2区域。其中i用来遍历数组，left用来标记0区域的最右侧，right用来标记2区域的最左侧。

        接下来进行分类讨论：如果nums[i]=0，我们让nums[left+1]与nums[i]进行交换，然后i++，left++，就能保证[left+1,i-1]区间还都是1，还可能有一种极端情况，就是i=left+1，自身与自身进行交换，还是得需要left和i++，综上我们就可以写成nums[++left]与nums[i++]进行交换。如果nums[i]=1，我们直接就可以i++就可以。如果nums[i]=2时，right的移动也可以参照上面left的处理，--right，但i不能++，因为i右侧是未遍历的区间，如果i++，就会跳过这个元素。当i=right时，结束循环。

        完整代码实现：

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

2.2. 排序数组

        这道题如果我们直接采用之前的快排思想是会超时的，因为如果数组里的元素都等于基准值key，这样数组元素就会跑到数组的最右侧，导致时间复杂度会退化成。

        我们接下来利用数组分三块的思想，将其划分为3个区域，<=key，=key，>=key。这样当基准值都等于key时，时间复杂度直接降为。

        接下来就是如何随机选择基准值。我们需要在数组下标中等概率地选择一个下标，那么我们就可以利用随机数种子，利用公式r%(right-left+1)+left求出随机下标。

        完整代码实现：

class Solution {public int[] sortArray(int[] nums) {Quicksort(nums, 0, nums.length - 1);return nums;}private void Quicksort(int[] nums, int l, int r) {if (l >= r) return;//作为递归结束的条件//数组分三块int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;while (i < right) {if (nums[i] < key) swap(nums, ++left, i++);else if (nums[i] == key) i++;else if (nums[i] > key) swap(nums, --right, i);}Quicksort(nums, l, left);Quicksort(nums, right, r);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

2.3. 数组中的第K个最大元素

        因为这道题让我们用时间复杂度为，所以我们的思路很明显要使用快速选择排序，也就是上一题的数组分三块与随机选择基准元素。那么这个第K大的元素就有可能落在三个区域内，我们设三个区域的元素个数分别为a、b、c。如果c>=k，那我们就直接去>key的这个区域去寻找；如果b+c>=k，就直接返回key；如果前两个都不成立，就去<key这个区间去寻找第k-b-c大的元素。

        完整代码实现：

class Solution {public int findKthLargest(int[] nums, int k) {return Quicksort(nums, 0, nums.length - 1, k);}private int Quicksort(int[] nums, int l, int r, int k) {if (l == r) return nums[l];//随机选择基准元素int key = nums[new Random().nextInt(r - l + 1) + l];//根据基准元素，把数组分为三块int left = l - 1, right = r + 1, i = l;while (i < right) {if (nums[i] < key) swap(nums, ++left, i++);else if (nums[i] == key) i++;else if (nums[i] > key) swap(nums, --right, i);}//分类讨论//区间:[l,left],[left+1,right-1],[right,r]int b = right - left - 1, c = r - right + 1;if (c >= k) return Quicksort(nums, right, r, k);else if (b + c >= k) return key;else return Quicksort(nums, l, left, k - b - c);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

2.4. 库存管理 III

        题目就是求数组中的最小的cnt个数。第一种解法，可以使用Arrays.sort()方法来对数组进行排序，找出前k个元素；第二种解法，利用大根堆，创建一个大小为k的大根堆，将数组的前k个元素丢进大根堆中，然后再将数组剩余的元素与堆顶元素比较，如果小就交换并调整堆，最后堆里面就是最小的k个数；第三个解法，就是快速选择算法。第一种解法的时间复杂度为，第二种解法的时间复杂度为，第三中解法的时间复杂度为。

        按照上一题的思路，将数组分为三块，三个区间内元素的个数分别为a、b、c。如果a>cnt，那么我们只需要去<key的区间去寻找；如果a+b>=cnt，此时的cnt一定是大于a的，那么最小的cnt个数，一定位于左侧两个区间，而中间区间又都是等于key的，所以不需要递归，直接++；如果前两个都不成立，直接去最右侧的区间去寻找第cnt-a-b个元素。

        完整代码实现：

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {Quicksort(stock,0,stock.length - 1,cnt);int[] ret = new int[cnt];for (int i = 0; i < cnt; i++) {ret[i] = stock[i];}return ret;}private void Quicksort(int[] nums, int l, int r, int k) {if(l >= r) return;//随机获取基准元素int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1,right = r + 1,i = l;//数组分三块while(i < right){if(nums[i] < key) swap(nums,++left,i++);else if (nums[i] == key) i++;else if (nums[i] > key) swap(nums,--right,i);}//分类讨论int a = left - l + 1,b = right - left - 1;if(a > k) Quicksort(nums,l,left,k);else if (a + b >= k) return;else Quicksort(nums,right,r,k - a - b);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}