算法

【体系学习005】归并排序1

Posted by Hilda on September 21, 2025

1.归并排序

  • 1）整体是递归，左边排好序+右边排好序+merge让整体有序
  • 2）让其整体有序的过程里用了排外序方法
  • 3）利用master公式来求解时间复杂度
  • 4）当然可以用非递归实现
\[T(N) = 2*T(N/2) + O(N^1)\]

根据master可知时间复杂度为\(O(N*logN)\)

merge过程需要辅助数组，所以额外空间复杂度为O(N)

归并排序的实质是把比较行为变成了有序信息并传递，比\(O(N^2)\)的排序快

2.题【小和累积和】

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。 例子： [1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：1 4左边比4小的数：1、3 2左边比2小的数：1 5左边比5小的数：1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16

题目链接【计算数组的小和】（ACM风格）：https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469?tab=note

题解：

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

import java.util.Scanner;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int MAXN = 100001;
    static int[] help = new int[MAXN];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            in.nextToken();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = (int)in.nval;
                in.nextToken();
            }
            long ans = smallSum(arr, 0, n - 1);
            out.println(ans);
        }
        out.flush();
        br.close();
        out.close();
    }

    public static long smallSum(int[] arr, int L, int R) {
        if (L >= R) {
            return (long)0;
        }
        int M = L + ((R - L) >> 1);
        return smallSum(arr, L, M) + smallSum(arr, M + 1, R) + merge(arr, L, M, R);
    }

    public static long merge(int[] arr, int L, int M, int R) {
        long ans = 0, sum = 0;
        for (int i = L, j = M + 1; j  <= R; j++) {
            while (i <= M && arr[i] <= arr[j]) {
                sum += ((long)arr[i++]);
            }
            ans += sum;
        }
        int a = L, b = M + 1, p = L;
        while ( a <= M && b <= R) {
            help[p++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= M) {
            help[p++] = arr[a++];
        }
        while (b <= R) {
            help[p++] = arr[b++];
        }
        for (int q = L; q <= R; q++) {
            arr[q] = help[q];
        }


        return ans;
    }
}

3.题【逆序对】

在一个数组中， 任何一个前面的数a，和任何一个后面的数b， 如果(a,b)是降序的，就称为逆序对 返回数组中所有的逆序对

题目链接：力扣LCR170-https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

解法：

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

class Solution {
    int[] help;
    public int reversePairs(int[] record) {
        int N = record.length;
        help = new int[N];
        return mergeSort(record, 0, N - 1);
    }
    public int mergeSort(int[] arr, int L, int R) {
        if (L >= R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return mergeSort(arr, L, M) + mergeSort(arr, M+1, R) + merge(arr, L, M, R);
    }

    public int merge(int[] arr, int L, int M, int R) {
        int ans = 0;
        for (int i = L, j = M + 1;i <= M;i++) {
            while (j <= R && arr[i] > arr[j]) j++;
            ans += (j - M - 1);
        }
        int a = L, b = M + 1, c = L;
        while (a <= M && b <= R) {
            help[c++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= M) {
            help[c++] = arr[a++];
        }
        while (b <= R) {
            help[c++] = arr[b++];
        }
        for (int k = L;k <= R;k++){
            arr[k] = help[k];
        }


        return ans;
    }
}

复杂度分析：

  • 时间复杂度 O(NlogN) ： 其中 N 为数组长度；归并排序使用 O(NlogN) 时间；

  • 空间复杂度 O(N) ： 辅助数组 help 占用 O(N) 大小的额外空间；

上面解法可以更加优化：

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

class Solution {
    int[] help;
    public int reversePairs(int[] record) {
        int N = record.length;
        help = new int[N];
        return mergeSort(record, 0, N - 1);
    }
    public int mergeSort(int[] arr, int L, int R) {
        if (L >= R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return mergeSort(arr, L, M) + mergeSort(arr, M+1, R) + merge(arr, L, M, R);
    }

    public int merge(int[] arr, int L, int M, int R) {
        int ans = 0;
        // for (int i = L, j = M + 1;i <= M;i++) {
        //     while (j <= R && arr[i] > arr[j]) j++;
        //     ans += (j - M - 1);
        // }
        int a = L, b = M + 1, c = L;
        // 直接在归并的过程中计算逆序对
        while (a <= M && b <= R) {
            if (arr[a] <= arr[b]) {
                help[c++] = arr[a++];
            } else {
                help[c++] = arr[b++];
                // arr[b]比arr[a]小，并且arr[a]是左半边未处理的第一个元素
                // 此时，左半边从arr[a]开始到M的所有元素都比arr[b]大
                ans += (M - a + 1);
            }
        }
        while (a <= M) {
            help[c++] = arr[a++];
        }
        while (b <= R) {
            help[c++] = arr[b++];
        }
        for (int k = L;k <= R;k++){
            arr[k] = help[k];
        }


        return ans;
    }
}

还有力扣493翻转对

解法：https://leetcode.cn/problems/reverse-pairs/description/

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

class Solution {

    int[] help;
    public int reversePairs(int[] nums) {
        int N = nums.length;
        help = new int[N];
        return mergeSort(nums, 0, N - 1);
    }
    public int mergeSort(int[] arr, int L, int R) {
        if (L >= R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return mergeSort(arr, L, M) + mergeSort(arr, M + 1, R) + merge(arr, L, M, R);
    }

    public int merge(int[] arr, int L, int M, int R) {
        int ans = 0;
        for (int i = L, j = M + 1;i <= M;i++) {
            while (j <= R && ((long)arr[i] > 2 * (long)arr[j])) j++;
            ans += (j - M - 1);
        }
        int a = L, b = M + 1, p = L;
        while (a <= M && b <= R) {
            help[p++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= M) {
            help[p++] = arr[a++];
        }
        while (b <= R) {
            help[p++] = arr[b++];
        }
        for (int q = L;q <= R;q++) {
            arr[q]  = help[q];
        }
        return ans;
    }
}

类似题目还有：

（填函数风格）https://www.nowcoder.com/practice/bb06495cc0154e90bbb18911fd581df6

4.非递归的归并排序

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

// 非递归方法实现
public static void mergeSort2(int[] arr) {
  if (arr == null || arr.length < 2) {
    return;
  }
  int N = arr.length;
  // 步长
  int mergeSize = 1;
  while (mergeSize < N) { // log N
    // 当前左组的，第一个位置
    int L = 0;
    while (L < N) {
      if (mergeSize >= N - L) {
        break;
      }
      int M = L + mergeSize - 1;
      int R = M + Math.min(mergeSize, N - M - 1);
      merge(arr, L, M, R);
      L = R + 1;
    }
    // 防止溢出
    if (mergeSize > N / 2) {
      break;
    }
    mergeSize <<= 1;
  }
}

其中merge方法上面都有，这里省略。

应用这个非递归版本的归并排序，去实现逆序对的解法：

比如测试链接：https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5

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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    int[] help;
    public int InversePairs (int[] nums) {
        
        int N = nums.length;
        help = new int[N];
        return (int)(mergeSort(nums) % 1000000007);
    }

    // 迭代
    public long mergeSort(int[] arr) {
        long ans = 0;
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int N = arr.length;
        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;
            while (L < N) {
                if (mergeSize >= N - L) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = M + Math.min(mergeSize, N - M - 1);
                ans += (long)merge(arr, L, M, R);
                L = R + 1;
            }
            if (mergeSize > N / 2) {
                break;
            }



            mergeSize <<= 1;
        }
        return ans;

    }

    public long merge(int[] arr, int L, int M, int R) {
        long ans = 0;
        int a = L, b = M + 1, i = L;
        while (a <= M && b <= R) {
            if (arr[a] <= arr[b]) {
                help[i++] = arr[a++];
            } else {
                help[i++] = arr[b++];
                ans += (long)( M - a + 1);
            }
        }
        while (a <= M) {
            help[i++] = arr[a++];
        }
        while (b <= R) {
            help[i++] = arr[b++];
        }
        for (int j = L;j <= R;j++) {
            arr[j] = help[j];
        }

        return ans;
    }
}
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 算法题库 Java基础 java集合 ollama工具 python爬虫
    FRIENDS