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));
    }

}