目录

1、分治算法简介

2、算法应用【leetcode】

2.1 题一：颜色分类

2.1.1 算法原理

2.2.1 算法代码

2.2 题二：排序数组——数组分三块原理

 2.2.1 算法原理

2.2.2 算法代码

2.3 题三：数组中的第K个最大元素

2.3.1 算法原理

2.3.2 算法代码

2.4 题四：库存管理III（原：剑指 Offer . 最小的k个数）

2.4.1 算法原理 

2.4.2 算法代码

---

1、分治算法简介

分治算法——简而言之，就是分而治之。

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成的程序算法，简单问题可用二分法完成。

将一个大问题划分称为若干个子问题，再将子问题划分为若干个更小的子问题，将一个个最小的子问题依次解决后，大问题也就顺势解决了。

2、算法应用【leetcode】

2.1 题一：颜色分类

. - 力扣（LeetCode）

2.1.1 算法原理

变量设置：

1. i：遍历数组
2. left：指向最后一个值为0的元素
3. right：指向第一个值为2的元素

变量区域含义：

1. [0,left]：全部是0
2. [left+1,i-1]：全部是1
3. [i,right-1]:未扫描
4. [right,n-1]：全部是2

注意：

1. if(nums[i]==0) --> swap(++left,i++);
2. if(nums[i]==2) --> swap(--right,i);//right-1位置的数值仍然是未知的，i不能++

2.2.1 算法代码

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

---

2.2 题二：排序数组——快排三路划分

. - 力扣（LeetCode）

 2.2.1 算法原理

本题可使用多种排序算法解决，这里演示快排的分治——数组分三块方法。

本次快排实现与以往不同的是——partition部分发生了改变：数组分三块。

1. 选取基准值key
2. 将数组依次分为<key、=key、>key，三部分
3. 这样一来，确定了=key这组数据在排完序后的固定位置
4. 数组分两块，在数据有序时快排将退化为O(N^2)
5. 而数组分三块，在数据有序时快排将稳定为O(N)

对于基准key的选取，我们采用随机数法优化法：

• key = nums[random.nextInt%(end-start+1)+start]；//(随机数法取基准)
• 随机数法相较于三数取中法更优

2.2.2 算法代码

class Solution {public int[] sortArray(int[] nums) {quickSort(nums);return nums;}public void quickSort(int[] nums) {quick(nums, 0, nums.length - 1);}public void quick(int[] nums, int s, int e) {if(s >= e) return;int key = nums[new Random().nextInt(e - s + 1) + s];int[] ret = partition(nums, s, e, key);quick(nums, s, ret[0]);quick(nums, ret[1], e);}//数组分三块public int[] partition(int[] nums, int l, int r, int key) {int i = l;int left = l - 1;int right = r + 1;while(i < right) {if(nums[i] < key) {swap(nums, ++left, i++);}else if(nums[i] == key) {i++;}else {swap(nums, --right, i);}}int[] ret = {left, right};return ret;}public void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

---

2.3 题三：数组中的第K个最大元素

. - 力扣（LeetCode）

2.3.1 算法原理

top-K问题的解法有三种：

1. 解法一：排序 --> O(N*logN)
2. 解法二：堆 --> O(N*logK)
3. 解法三：快速选择算法 --> O(N)（基于快速排序）

这里讲解最优的快速选择算法。

快速选择算法就是基于上题快排做出了一点小调整，对于三个区域分类讨论，选出第K个最大值。

1. c >= k ，去[r，e]找第k大的值
2. c+b >= k，返回key
3. ①和②都不成立，则去[s，l]找第k-b-c大的值 

2.3.2 算法代码

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

---

2.4 题四：库存管理III（原：剑指 Offer . 最小的k个数）

. - 力扣（LeetCode）

2.4.1 算法原理 

整体思想：将数组的前k个数保证为最小的k个数即可。

随机数取基准 -> 将数组划分三块 -> 如下分类讨论

• ①：a > k，qsort(nums, s, left);
• ②：a +b >= k,，返回
• ③：①、②都不符合，qsort(nums, right, e, k - a - b);

2.4.2 算法代码

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

---

3、分治——归并排序

3.1  排序数组

. - 力扣（LeetCode）

3.1.1 算法代码

对于归并排序的原理，这里就不再赘述了。

class Solution {int[] tmp;public int[] sortArray(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}public void mergeSort(int[] nums, int s, int e) {if(s >= e) return;//根据中间节点划分区间int mid = (s + e) / 2;//把左右区间排序mergeSort(nums, s, mid);mergeSort(nums, mid + 1, e);//合并两个有序数组merge(nums, s, mid, e);}public void merge(int[] nums, int s, int mid, int e) {int s1 = s, e1 = mid, s2 = mid + 1, e2 = e;int k = 0;while(s1 <= e1 && s2 <= e2) tmp[k++] = nums[s1] <= nums[s2] ? nums[s1++] : nums[s2++];//处理没有遍历完的数组while(s1 <= e1) tmp[k++] = nums[s1++];while(s2 <= e2) tmp[k++] = nums[s2++];for(int i = s; i <= e; i++) nums[i] = tmp[i - s]; }
}

---

END