05、算法与数据结构 - 实战：递归、归并排序与快速排序
递归实现取数组最大值
1、 当前递归，求一个mid中间位置；
2、 最侧递归，获取左侧的max；
3、 右侧递归，获取右侧的max；
4、 两个max，pk一下，返回最大的max；
base case：left == right，就返回arr[left]
Master公式求递归的时间复杂度
master公式使用的前提时，子问题的规模是一致的
T(N) = a * T(N/b) + O(N ^ d)
N/b就是子问题规模，T(N/b) 就是子问题
如果log(b,a) < d，复杂度为O(N ^ d)
如果log(b,a) > d，复杂度为O(N ^ log(b,a))
如果log(b,a) == d，复杂度为O(N ^ d * logN)
递归实现归并排序
1、 每个递归里面，取中点，切分后继续递归；
2、 直到碰到basecase：l==r；
3、 递归返回后，左右两侧都是局部有序的，用一个help数组进行合并，左右两个指针，谁小先拷贝谁，合并完成后，把help数组copy回原数组中；
/**
* 递归实现归并排序
*/
public class MergeSort01 {
public static void sort(int[] arr) {
process(arr, 0, arr.length-1);
}
private static void process(int[] arr, int l, int r) {
if (l == r) return; // 一个数，天然有序，返回
int mid = l + ((r - l) >> 1); //取中点
process(arr, l, mid); //递归切分
process(arr, mid + 1, r); //递归切分
merge(arr, l, mid, r); //此时左右两边都局部有序，进行合并
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int a = l;
int b = mid + 1;
//不断的比较左右两边的数，谁小谁排前面，放入临时数组help
while (a <= mid && b <= r) help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
//如果右边的数组放完，左边有剩余，把左边的全部排到后面
while (a <= mid) help[i++] = arr[a++];
//如果左边的数组放完，右边有剩余，把右边的全部排到后面
while (b <= r) help[i++] = arr[b++];
//按照help数组中的顺序，把排好序的元素放回到原数组arr中
for (i = 0; i < help.length; i++) arr[l + i] = help[i];
}
}
遍历实现归并排序
定义一个代表分组合并的长度len，每次len * 2
每个len长度内的子数组，左右进行合并
然后len的长度扩大，再左右进行合并
直到len扩到到arr.length，合并完后就整体有序
package _01基础._05归并排序;
import java.util.Arrays;
/**
* 遍历实现归并排序
*/
public class MergeSort02 {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
//步长从2开始，2->4->8->......
int len = 2;
//步长达到数组长度*2就返回
while (len < arr.length * 2) {
int l = 0;
//按步长进行迭代递归
while (l < arr.length) {
int mid = l + ((len >> 1) - 1);
// 只剩下左组，右组一个数都没有，则跳过
if (mid >= arr.length - 1) break;
int r = Math.min(l + len - 1, arr.length -1);
merge(arr, l, mid, r);
l = r + 1;
}
//防止int类型溢出
if (len > arr.length) {
break;
}
len <<= 1;
}
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int a = l;
int b = mid + 1;
//不断的比较左右两边的数，谁小谁排前面，放入临时数组help
while (a <= mid && b <= r) help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
//如果右边的数组放完，左边有剩余，把左边的全部排到后面
while (a <= mid) help[i++] = arr[a++];
//如果左边的数组放完，右边有剩余，把右边的全部排到后面
while (b <= r) help[i++] = arr[b++];
//按照help数组中的顺序，把排好序的元素放回到原数组arr中
for (i = 0; i < help.length; i++) arr[l + i] = help[i];
}
}
求数组最小和
就是给定一个数组，然后求数组中每个数的左边比它小的数的累加和，然后把这些累加和再累加再一起，作为结果返回
求数组最小和，普通做法就是遍历每一个数，然后把当前这个数左边比它小的数累加，得到结果值，该值就是数组最小和。
可以转化一下：一个数，右边有多少个数比它大，就累加多少次这个数到结果中
利用归并排序，左边比较小的时候，在merge左边的数之前，先结算一下
注意：左右相等，先merge右边的，因为merge完右边，下一个右边的数就会比左边的大，左边的就可以结算，否则就会把左边的错过
/**
* 求数组最小和：
* 一个数组中，一个数左边比它小的数之和，称为小和，数组中所有数的小和加起来，称为数组小和
*/
public class MergeSort03 {
public static int sort(int[] arr) {
return process(arr, 0, arr.length-1);
}
private static int process(int[] arr, int l, int r) {
if (l == r) return 0; // 一个数，天然有序，返回
int mid = l + ((r - l) >> 1); //取中点
return process(arr, l, mid) + //递归切分;
process(arr, mid + 1, r) + //递归切分
merge(arr, l, mid, r); //此时左右两边都局部有序，进行合并
}
private static int merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int a = l;
int b = mid + 1;
int res = 0;
//数组最小和的求解，转化为：求一个数右边有多少个数比它大，然后就将值(当前数 * 右边比它大的数的个数)累加到res中
while (a <= mid && b <= r) {
//如果左边数，比又变小，则从下标b开始，直到下标r，这么多个数都比arr[a]大
if (arr[a] < arr[b]) {
res += arr[a] * (r - b + 1);
}
//只有左边比右边小，才拷贝左边，否则都拷贝右边
help[i++] = arr[a] < arr[b] ? arr[a++] : arr[b++];
}
//如果右边的数组放完，左边有剩余，把左边的全部排到后面
while (a <= mid) help[i++] = arr[a++];
//如果左边的数组放完，右边有剩余，把右边的全部排到后面
while (b <= r) help[i++] = arr[b++];
//按照help数组中的顺序，把排好序的元素放回到原数组arr中
for (i = 0; i < help.length; i++) arr[l + i] = help[i];
return res;
}
}
求数组逆序对个数
逆序对的意思就是左边的数比右边的数小，这样的一对数，就是逆序对
其实就是在求数组中的每个数，右边有多少个数比它小，然后把这些个数累加结果返回
一样可以通过归并处理
左右两个数组，从右往左merge，谁大先merge谁，merge左边的时候，就可以结算右边比它小的有多少个
注意：相等的时候也是先merge右边的
/**
* 求数组中的逆序对个数
*/
public class MergeSort04 {
public static int sort(int[] arr) {
return process(arr, 0, arr.length-1);
}
private static int process(int[] arr, int l, int r) {
if (l == r) return 0; // 一个数，天然有序，返回
int mid = l + ((r - l) >> 1); //取中点
return process(arr, l, mid) + //递归切分
process(arr, mid + 1, r) + //递归切分
merge(arr, l, mid, r); //此时左右两边都局部有序，进行合并
}
private static int merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int a = l;
int b = mid + 1;
int res = 0;
while (a <= mid && b <= r) {
//右边的数比左边的数小，则左边数组从下标a开始，到下标mid，这么多个数都可以与arr[b]组成逆序对
if (arr[a] > arr[b]) {
res += (mid - a + 1);
}
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
//如果右边的数组放完，左边有剩余，把左边的全部排到后面
while (a <= mid) help[i++] = arr[a++];
//如果左边的数组放完，右边有剩余，把右边的全部排到后面
while (b <= r) help[i++] = arr[b++];
//按照help数组中的顺序，把排好序的元素放回到原数组arr中
for (i = 0; i < help.length; i++) arr[l + i] = help[i];
return res;
}
}
求数组中的每个数右边有多少个数乘2之后依然小于它的，返回这种数的个数
就是看一下数组中的每个数，右边有多少个数是乘以2之后都还是比它小的，然后就把这些个数累加再一起，作为结果返回
解法也是差不多，不过这个merge的时候，就正常merge就行了
但是在merge之前，还要遍历一下左组的每一个数，看右组有多少个数乘二之后比它还小
有一个windowR指针，滑到乘二之后不比左边小，就停，那么结算就是windowR - m - 1
windowR是不用回退的，因为左右两边都是局部有序，所以之前划过的数一定是满足规则的
/**
* 求数组中的每个数右边有多少个数乘2之后依然小于它的，返回这种数的个数
*/
public class MergeSort05 {
public static void sort(int[] arr) {
process(arr, 0, arr.length-1);
}
private static int process(int[] arr, int l, int r) {
if (l == r) return 0; // 一个数，天然有序，返回
int mid = l + ((r - l) >> 1); //取中点
return process(arr, l, mid) //递归切分
+ process(arr, mid + 1, r) //递归切分
+ merge(arr, l, mid, r); //此时左右两边都局部有序，进行合并
}
private static int merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
/*
归并的步骤都一样，只是再merge前，先搞一下
*/
int windowR = mid + 1; // 右边窗口，滑到乘2大于左，就停，那么计算就是：windowR - m - 1
int res = 0;
for (int i = l; i <= mid; i++) {
while (windowR <= r && arr[windowR] * 2 < arr[i]) windowR++;
res += (windowR - mid - 1);
}
int i = 0;
int a = l;
int b = mid + 1;
//不断的比较左右两边的数，谁小谁排前面，放入临时数组help
while (a <= mid && b <= r) help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
//如果右边的数组放完，左边有剩余，把左边的全部排到后面
while (a <= mid) help[i++] = arr[a++];
//如果左边的数组放完，右边有剩余，把右边的全部排到后面
while (b <= r) help[i++] = arr[b++];
//按照help数组中的顺序，把排好序的元素放回到原数组arr中
for (i = 0; i < help.length; i++) arr[l + i] = help[i];
return res;
}
}
区间和的个数
leetcode第327题
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
https://leetcode.cn/problems/count-of-range-sum/
思路： 1、 求一个子数组的累加和，例如[l…r]，相当于求sum[r]-sum[l-1]，sum是前缀和数组；
2、 可以以每个数作为结尾，看有多少个子数组达标；
3、 接着2，转换一下思维，以nums[i]=x为结尾有多少个子数组达标，其实等于[0…i-1]有多少个数组前缀和在[x-upper,x-lower]上；
4、 接着3，先生成前缀和数组sum，再对sum进行merge排序，在每一个merge前，去搞步骤3的事情，搞完在merge；
5、 每一个merge前搞的事情就是，遍历右组每一个数，看左组在[x-upper,x-lower]上的个数有多少个；
/**
* https://leetcode.cn/problems/count-of-range-sum/
* 力扣327题
* 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
*
* Created by huangjunyi on 2022/11/19.
*/
public class MergeSort06 {
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
/*
思路：
1、求一个子数组的累加和，例如[l...r]，相当于求sum[r] - sum[l - 1]，sum是前缀和数组
2、可以以每个数作为结尾，看有多少个子数组达标
3、接着2，转换一下思维，以nums[i]=x为结尾有多少个子数组达标，其实等于[0...i-1]有多少个数组前缀和在[x-upper, x-lower]上
4、接着3，先生成前缀和数组sum，再对sum进行merge排序，在每一个merge前，去搞步骤3的事情，搞完在merge
5、每一个merge前搞的事情就是，遍历右组每一个数，看左组在[x-upper, x-lower]上的个数有多少个
*/
// 求出前缀和数组
int N = nums.length;
long[] sum = new long[N];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
// 利用前缀和数组 + merge排序，求出达标的子数组个数
return process(sum, 0, N - 1, lower, upper);
}
/**
* 求在l到r的范围上，有多少个累加和在[lower, upper]范围上的子数组
* @param sum 前缀和数组
* @param l 左边界
* @param r 右边界
* @param lower 范围下限
* @param upper 范围上限
* @return
*/
private int process(long[] sum, int l, int r, int lower, int upper) {
// 这个是检查0...l这个子数组是否达标
if (l == r) return sum[l] >= lower && sum[l] <= upper ? 1 : 0;
int m = l + ((r - l) >> 1);
return process(sum, l, m, lower, upper)
+ process(sum, m + 1, r, lower, upper)
+ merge(sum, l, m, r, lower, upper);
}
/**
* merge左右两侧子数组，使其整体有序，
* 并返回对与右组中的每一个数而言，左组中有多少个数在[x - upper, x - lower]范围上
* @param sum 前缀和数组
* @param l 左边界
* @param m 中点
* @param r 右边界
* @param lower 范围下限
* @param upper 范围上限
* @return
*/
private int merge(long[] sum, int l, int m, int r, int lower, int upper) {
// [windowL, windowR)，[x-upper, x-lower]的个数等于windowR - windowL
int windowL = l; // 滑到大于等于x-upper的时候停
int windowR = l; // 划出x-lower的时候停
int res = 0;
for (int i = m + 1; i <= r; i++) {
long min = sum[i] - upper; // x-upper
long max = sum[i] - lower; // x-lower
while (windowR <= m && sum[windowR] <= max) windowR++;
while (windowL <= m && sum[windowL] < min) windowL++;
res += windowR - windowL; // 累加结果
}
long[] help = new long[r - l + 1];
int left = l;
int right = m + 1;
int index = 0;
while (left <= m && right <= r) {
if (sum[left] <= sum[right]) {
help[index++] = sum[left++];
} else {
help[index++] = sum[right++];
}
}
while (left <= m) {
help[index++] = sum[left++];
}
while (right <= r) {
help[index++] = sum[right++];
}
index = 0;
for (int i = l; i <= r; i++) {
sum[i] = help[index++];
}
return res;
}
}
}
荷兰国旗问题
给定一个数组，并且给定一个基准值，数组中小于该值的数放左边，大于该值的数放右边，等于该值的数放中间，然后返回中间等于该值的区域的左右边界。
定一个low指针，表示小于区域的边界，初始值为-1
定义一个high指针，相当于大于区域的边界
定一个一个cur指针，遍历数组每一个数，假设基准值为右边界r对应的数arr[r]：
1、 如果arr[cur]==arr[r]，cur++；
2、 如果arr[cur]<arr[r]，arr[cur]与arr[low+1]交换，low往右扩一位，cur++；
3、 如果arr[cur]>arr[r]，arr[cur]与arr[high-1]交换，high往左扩一位，cur不动；
4、 直到cur装上high，停，arr[high]与arr[r]交换；
整个过程，相当于cur遍历数组，往左右两边发货
/**
* 荷兰国旗问题：
* 给定一个数组，并且给定一个基准值，数组中小于该值的数放左边，大于该值的数放右边，等于该值的数放中间
* 然后返回中间等于该值的区域的左右边界
*/
public class QuickSort01 {
public static int[] partition(int[] arr, int l, int r) {
if (l > r) return new int[]{
-1, -1};
if (l == r) return new int[]{
l, r};
int low = l - 1; //小于基准值的区域的右边界
int high = r; //大于基准值的区域的左边界，以arr[r]作为基准值，先把他包裹在右区域内，最后再处理
int i = l;
while (i < high) {
//小于基准值，把arr[i]与小于区域的右一个数交换，小于区域往右括一位，i跳到下一位
if (arr[i] < arr[r]) swap(arr, i++, ++low);
//大于基准值，把arr[i]与大于区域左边一个数交换，大于区域往左括一位，i不动，因为新换过来的这个数还没看过
else if (arr[i] > arr[r]) swap(arr, i, --high);
//等于基准值，i跳下一位
else i++;
}
//处理arr[r]，与大于区域的左边界的数交换，相当于等于区域往右括一位
swap(arr, high, r);
return new int[]{
low + 1, high};
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
随机快排
/**
* 随机快排
*/
public class QuickSort02 {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
process(arr, 0, arr.length - 1);
}
private static void process(int[] arr, int l, int r) {
if (l >= r) return;
//先对数组做分区处理，得出三个区域，[小于基准值区域|等于基准值区域|大于基准值区域]
int[] partition = partition(arr, l, r);
//递归处理左区域
process(arr, l, partition[0] - 1);
//递归处理右区域
process(arr, partition[1] + 1, r);
}
private static int[] partition(int[] arr, int l, int r) {
//在指定区域内，随机选取一个数，作为基准值
swap(arr, l + (int)(Math.random() * (r - l + 1)), r);
if (l > r) return new int[]{
-1, -1};
if (l == r) return new int[]{
l, r};
int low = l - 1; //小于基准值的区域的右边界
int high = r; //大于基准值的区域的左边界，以arr[r]作为基准值，先把他包裹在右区域内，最后再处理
int i = l;
while (i < high) {
//小于基准值，把arr[i]与小于区域的右一个数交换，小于区域往右括一位，i跳到下一位
if (arr[i] < arr[r]) swap(arr, i++, ++low);
//大于基准值，把arr[i]与大于区域左边一个数交换，大于区域往左括一位，i不动，因为新换过来的这个数还没看过
else if (arr[i] > arr[r]) swap(arr, i, --high);
//等于基准值，i跳下一位
else i++;
}
//处理arr[r]，与大于区域的左边界的数交换，相当于等于区域往右括一位
swap(arr, high, r);
//返回等于基准值区域的左右边界
return new int[]{
low + 1, high};
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
快速排序非递归版本
思路就是用一个栈结构去模拟系统底层的递归处理过程
/**
* 快速排序非递归版本
* Created by huangjunyi on 2022/11/19.
*/
public class QuickSort03 {
private static class Op {
int l; // 排序范围左边界
int r; // 排序范围右边界
public Op(int l, int r) {
this.l = l;
this.r = r;
}
}
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
int N = arr.length;
/*
用一个栈，去模拟系统底层的递归处理过程
*/
LinkedList<Op> stack = new LinkedList<>();
stack.push(new Op(0, N - 1));
while (!stack.isEmpty()) {
Op op = stack.pop();
if (op.l >= op.r) continue;
swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
int[] range = partition(arr, op.l, op.r);
stack.push(new Op(op.l, range[0] - 1));
stack.push(new Op(range[1] + 1, op.r));
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int[] partition(int[] arr, int l, int r) {
int less = -1;
int more = r;
int cur = 0;
while (cur != more) {
if (arr[cur] < arr[r]) {
swap(arr, cur++, ++less);
} else if (arr[cur] > arr[r]) {
swap(arr, cur, --more);
} else {
cur++;
}
}
swap(arr, more, r);
return new int[] {
less + 1, more};
}
public static void main(String[] args) {
int[] arr1 = {
9,4,884,1,19,19,1,84,8,45,1,1,519,181,9};
int[] arr2 = {
9,4,884,1,19,19,1,84,8,45,1,1,519,181,9};
sort(arr1);
System.out.println(Arrays.toString(arr1));
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
}
}