【算法自由之路】归并、快排

归并排序

对于归并排序来说有两种方式，一种是递归方式，一种是非递归的循环方式。

整体思想是我先让数组左右两部分有序，然后两个有序部分合并进而整体有序，称这个过程为归并。

将大问题分为同类型的小规模问题

归并排序递归算法

public class MargeSort {

    public static void sort(int[] arr) {
        processSort(arr, 0, arr.length - 1);
    }

    // 递归含义 使 [L,R] 范围有序
    public static void processSort(int[] arr, int L, int R) {
        if (arr.length < 2 || L == R) {
            // 结束条件
            return;
        }
        int mid = L + ((R - L) >> 1);
        processSort(arr, L, mid);
        processSort(arr, mid + 1, R);
        marge(arr, L, mid, R);

    }

    /**
     * @Description: 合并 [L ,mid] [mid+1,R] 两个有序数组
     * @Param arr
     * @Param L
     * @Param mid
     * @Param R
     * @Return void
     */
    private static void marge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int lStart = L;
        int rStart = mid + 1;
        int i = 0;
        while (lStart <= mid && rStart <= R) {
            help[i++] = arr[lStart] < arr[rStart] ? arr[lStart++] : arr[rStart++];
        }
        while (lStart <= mid) {
            help[i++] = arr[lStart++];
        }
        while (rStart <= R) {
            help[i++] = arr[rStart++];
        }
        i = 0;
        for (int j = L; j <= R; j++) {
            arr[j] = help[i++];
        }
    }

    public static void main(String[] args) {
        int[] arr;
        int[] arr2;
        SelectionSort selectionSort = new SelectionSort();
        Random random = new Random();
      	// 对数器
        for (int i = 0; i < 1000; i++) {
            int len = random.nextInt(20) + 5;
            arr = new int[len];
            arr2 = new int[len];
            for (int j = 0; j < len; j++) {
                int item = random.nextInt(100);
                arr[j] = item;
                arr2[j] = item;
            }
            sort(arr);
            selectionSort.sort(arr2);
            for (int k = 0; k < len; k++) {
                if (arr[k]!=arr2[k]){
                    System.out.println("error");
                    return;
                }
            }
        }
        System.out.println("success");
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

归并排序，时间复杂度 O(N*longN) , 空间复杂度 O(N)

归并排序非递归算法

递归算法运行起来有点像一颗树的形状，从一开始的大问题，二分为两个小问题，然后继续分，开枝散叶最后汇总。

从 JVM 层面理解，每个线程的执行，都会对应分配一个线程栈内存区域，这个区域每个方法执行都会分配一块栈帧内存空间并将其压入栈，直到执行完成则弹出，对应到递归过程直到你触发到递归出口，否则就会一直循环调用子方法拆解问题并入栈。

而将递归算法改为非递归算法的过程，有点像这个的逆过程，有点像一颗倒着的树，循序代替了栈的功能。

  public static void sort2(int[] arr) {
        // 子合并区域以 1 开始
        int range = 1;
      	// 如果子合并区域小于数组则已经完成排序，子合并区域每次 2 倍增长
        while (range < arr.length) {
            int start = 0;
            // 每次参与合并的步长 是 range 的两倍
            int step = range << 1;

            // 如果后续子数组不够两个合并区则最后一部分无需排序，已经有序
            while (start + range < arr.length) {

                int L = start;
                int mid = start + range - 1;
                // 防止 R 越界，即数组最后不够一个 range 时
                int R = Math.min(start + step - 1, arr.length - 1);
                marge(arr, L, mid, R);
                start = R + 1;
            }
            range = step;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

大 while 是 O(longN) 内部 while 是 O(N) 所以总时间复杂度和递归一样 O(N*longN) 空间复杂度 O(N)

归并排序的应用

可解决 某一类问题，可以抽象为数组中左边有多少数比某个数大，反之亦然。

比如 数组小和问题 给定一个数组，任意一个位置 i ，该元素前面比它小的数的和为该数的小和，所有数小和的累加为数组小和。

package algorithmic.base;

import util.CommonUtil;
import util.RandomUtil;

import java.util.Arrays;

// 数组最小和问题，归并排序应用
public class MargeSortGetMinSum {

	// 返回 [L.R] 范围的数组小和
    public static int processSortGetMin(int[] arr, int L, int R) {
        if (arr.length < 2 || L == R) {
            // 结束条件
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        // 分解子问题
        int lMin = processSortGetMin(arr, L, mid);
        int rMin = processSortGetMin(arr, mid + 1, R);
        // 左右合并得到的小和
        int mMin = margeGetMinSum(arr, L, mid, R);
        return mMin + lMin + rMin;

    }

    // 获取小和
    private static int margeGetMinSum(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int lStart = L;
        int rStart = mid + 1;
        int result = 0;
        int i = 0;
        while (lStart <= mid && rStart <= R) {

            if (arr[lStart] < arr[rStart]) {
                int current = help[i++] = arr[lStart++];
                // 抽象为右组有多少个数比当前数大，可以省去遍历相加
                result += current * (R - rStart + 1);
            } else {
                // 相等时，先入右组数，更新游标
                help[i++] = arr[rStart++];
            }
        }
        while (lStart <= mid) {
            help[i++] = arr[lStart++];
        }
        while (rStart <= R) {
            help[i++] = arr[rStart++];
        }
        i = 0;
        for (int j = L; j <= R; j++) {
            arr[j] = help[i++];
        }
        return result;
    }

    // 归并方法，时间复杂度 O(N*longN)
    public static int getMinSum(int[] arr) {
        return processSortGetMin(arr, 0, arr.length - 1);
    }

    // 暴力方法 O(N^2)
    public static int getMinSumSimple(int[] arr) {
        int sum = 0;

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    sum += arr[j];
                }
            }
        }

        return sum;
    }

    public static void main(String[] args) {

        for (int i = 0; i < 1000; i++) {
            int[] arr = RandomUtil.randomArr();
            int[] arr2 = CommonUtil.copyArr(arr);
            int[] arr3 = CommonUtil.copyArr(arr);
            int minSumSimple = getMinSumSimple(arr);
            int minSum = getMinSum(arr2);
            if (minSum != minSumSimple) {
                System.out.println(Arrays.toString(arr3));
                System.out.println(Arrays.toString(arr2));
                System.out.println(Arrays.toString(arr));
                System.out.println("error marge=" + minSum + " simple=" + minSumSimple);
                return;
            }
        }
        System.out.println("success");

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

这里可以使用归并来做的思路很简单，在整个归并过程中，左右组的元素都会经历一次 marge 过程，在这个过程中可以处理获取左右组的关系，并且排序过后不会影响后续的 marge 中左右位置的关系，利用子组有序的特性，将题目小和累加同等转换为当前数右边有多少个数比它大 result += current * (R - rStart + 1)

逆序对问题

在一个数组中，任意 i 位置数如果大于任意后置位的数，则与该数组成一个逆序对，给定一个数组求数组中有多少逆序对

如对于数组 [1,3,4,5,2]
逆序对有 [3,2] [4,2] [5,2] 结果为 3
1
2

这里转换为对于数组中某个数，这个数前面有多少个数比它大，即在每个归并过程中右组元素归并时计算左组还剩多少元素

package algorithmic.base.marge_sort;

import util.CommonUtil;
import util.RandomUtil;

import java.util.Arrays;

//**逆序对问题**
//
//在一个数组中，任意 i 位置数 对于任意后置位的数如果大于则与该数组成一个逆序对，给定一个数组求数组中有多少逆序对
//
//```java
//如对于数组 [1,3,4,5,2]
//逆序对有 [3,2] [4,2] [5,2] 结果为 3
//```
public class MargeSortReversePair {


    public static int reversePairNumSimple(int[] arr) {
        int num = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) {
                    num++;
                }
            }
        }
        return num;
    }


    public static int reversePairNum(int[] arr) {
        return processSort(arr, 0, arr.length - 1);
    }

    // 递归含义 使 [L,R] 范围有序
    public static int processSort(int[] arr, int L, int R) {
        if (arr.length < 2 || L == R) {
            // 结束条件
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return processSort(arr, L, mid) +
                processSort(arr, mid + 1, R) +
                marge(arr, L, mid, R);

    }

    /**
     * @Description: 合并 [L ,mid] [mid+1,R] 两个有序数组
     * @Param arr
     * @Param L
     * @Param mid
     * @Param R
     * @Return void
     */
    private static int marge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int lStart = L;
        int rStart = mid + 1;
        int i = 0;
        int num = 0;
        while (lStart <= mid && rStart <= R) {
            if (arr[lStart] <= arr[rStart]) {
                // 相等时，先入左组数，更新游标
                help[i++] = arr[lStart++];
            } else {
                // 抽象为左组有多少个数比当前数大
                num += (mid - lStart + 1);
                help[i++] = arr[rStart++];
            }
        }
        while (lStart <= mid) {
            help[i++] = arr[lStart++];
        }
        while (rStart <= R) {
            help[i++] = arr[rStart++];
        }
        i = 0;
        for (int j = L; j <= R; j++) {
            arr[j] = help[i++];
        }
        return num;
    }

    public static void main(String[] args) {

        for (int i = 0; i < 10000; i++) {
            int[] arr = RandomUtil.randomArr();
            int[] arr2 = CommonUtil.copyArr(arr);
            int reversePairNum = reversePairNum(arr);
            int reversePairNumSimple = reversePairNumSimple(arr2);
            if (reversePairNum != reversePairNumSimple) {
                System.out.println(Arrays.toString(arr2));
                System.out.println("error reversePairNum=" + reversePairNum +
                        " reversePairNumSimple=" + reversePairNumSimple);
                return;
            }
        }
        System.out.println("success");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

快速排序

快排的核心思想是分区，那最重要的就是分区算法。

给定一个值 x ，将大于 x 的值放到数组右边，小于的放到左边，这个过程就是分区

一次分区过程就相当于确定了 x 值在整个数组中的位置，刨去 x 在去两端进行分区，直到所有分区完毕即完成了排序

当我们一次分区搞定一个数，快排的时间复杂度为 O(N^2) , 只有在一次分区搞定多个相等数时才是我们想要的快排，同时对于 x 的取值要随机，此时的时间复杂度为 O(N*logN)

普通分区算法

思路是定义一个小于等于区，一开始为数组 L 范围 -1 ，遍历数组推进小于等于区的扩张

    // 在 [L,R] 上进行分区 返回等于数的位置
    public static int partition(int[] arr, int L, int R) {
        // 小于等于区下标
        int minEqIndex = L - 1;
        for (int i = L; i <= R; i++) {
            if (arr[i] <= arr[R]) {
                swap(arr, i, ++minEqIndex);
            }
        }
        return minEqIndex;
    }
1
2
3
4
5
6
7
8
9
10
11

荷兰国旗分区算法

区别是我们将数组分为三份，小于区，等于区，大于区

这样我们一次分区就搞定了一组等于区的数

// 在 [L,R] 上进行分区 返回等于区下标
    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 minEqIndex = L - 1;
        // 大于区下标
        int maxEqIndex = R;
        int index = L;
        // 随机取一个数
        int some = random.nextInt(R - L + 1) + L;
        swap(arr, some, R);
        while (index < maxEqIndex) {
            if (arr[index] < arr[R]) {
                swap(arr, index++, ++minEqIndex);
            } else if (arr[index] > arr[R]) {
                swap(arr, index, --maxEqIndex);
            } else {
                index++;
            }
        }
        swap(arr, R, maxEqIndex);
        return new int[]{minEqIndex + 1, maxEqIndex};
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

初版快排

import util.CommonUtil;
import util.RandomUtil;
import java.util.Arrays;

public class QuickSortSimple {


    public static void sort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    // [L,R] 范围有序
    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int m = partition(arr, L, R);
        process(arr, L, m - 1);
        process(arr, m + 1, R);
    }

    // 在 [L,R] 上进行分区 返回等于数的位置
    public static int partition(int[] arr, int L, int R) {
        // 小于等于区下标
        int minEqIndex = L - 1;
        for (int i = L; i <= R; i++) {
            if (arr[i] <= arr[R]) {
                swap(arr, i, ++minEqIndex);
            }
        }
        return minEqIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            int[] arr = RandomUtil.randomArr();
            int[] arr2 = CommonUtil.copyArr(arr);
            MargeSort.sort(arr);
            sort(arr2);
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] != arr2[j]) {
                    System.out.println(Arrays.toString(arr));
                    System.out.println(Arrays.toString(arr2));
                    System.out.println("error");
                    return;
                }
            }
        }
        System.out.println("success");
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

经典快排

import util.CommonUtil;
import util.RandomUtil;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    public static final Random random = new Random();

    public static void sort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    // [L,R] 范围有序
    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] pair = partition(arr, L, R);
        process(arr, L, pair[0] - 1);
        process(arr, pair[1] + 1, R);
    }

    // 在 [L,R] 上进行分区 返回等于区下标
    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 minEqIndex = L - 1;
        // 大于区下标
        int maxEqIndex = R;
        int index = L;
        // 随机取一个数
        int some = random.nextInt(R - L + 1) + L;
        swap(arr, some, R);
        while (index < maxEqIndex) {
            if (arr[index] < arr[R]) {
                swap(arr, index++, ++minEqIndex);
            } else if (arr[index] > arr[R]) {
                swap(arr, index, --maxEqIndex);
            } else {
                index++;
            }
        }
        swap(arr, R, maxEqIndex);
        return new int[]{minEqIndex + 1, maxEqIndex};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            int[] arr = RandomUtil.randomArr();
            int[] arr2 = CommonUtil.copyArr(arr);
            MargeSort.sort(arr);
            sort(arr2);
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] != arr2[j]) {
                    System.out.println(Arrays.toString(arr));
                    System.out.println(Arrays.toString(arr2));
                    System.out.println("error");
                    return;
                }
            }
        }
        System.out.println("success");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

相关阅读:
小程序入门笔记（一）黑马程序员前端微信小程序开发教程
 在使用了spring-cloud-starter-gateway后，为什么还会发生cors问题
 计算机网络（六）：应用层
 （三）使用 Vue 脚手架
 Mysql索引分类及其使用实例
 刷爆 LeetCode 双周赛 100，单方面宣布第一题最难
 神经网络属于人工智能的,人工智能神经系统是
 【面试题】—— 笔试题（4题）
LeetCode47：全排列②
山东大学软件学院深度学习期末回忆版
原文地址：https://blog.csdn.net/w903328615/article/details/127839873