SnowDawn'Home
0%

归并排序

发表于 更新于 分类于

基本思路

归并排序，即通过先递归再排序的方法来实现排序。

  • 将一组数从中间分为两组，分别进行递归
  • 在不断的分组中，最终每一组都被分割为只有一个数，可以看作是本组完成了排序
  • 递归之后一步步将每一组合并
  • 合并的过程中使用双指针算法，取两个指针，分别指向要合并的两个组的开头，比较指针所指数的大小，将较小的放入临时数组 t m p [ ] , 并且指针向后移动，以此类推，放完一个，再将剩下的一组直接全部放入 t m p[ ]。
  • 最后将 已经完成排序的临时数组 放入最终数组的相应位置

代码实现模板

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
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N];
int tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r); //递归 ， 先把每一组都排完 ，分到最后每一组只有一个了，也就是排好了

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)              //两组指针指着的数谁大就把谁塞进去。
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];                   //把较大组剩下的都排进去

    for (int i = l, j = 0; i <= r; i++, j++) //l是这个组的开始，把这个组的tmp都塞进去。
        q[i] = tmp[j];
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);

    return 0;
}

应用例题：逆序对的数量

逆序对： 一个数组中 ， 下标 i ， j 两个数 ，满足 ：i < j 且 a[ i ] > a[ j ]

用归并排序的过程完成逆序对数量的计算。

进行归并操作时 , 其中一个判断正好符合逆序的定义

1
2
3
4
5
6
7
8
while (i <= mid && j <= r)              //两组指针指着的数谁大就把谁塞进去。
       if (q[i] <= q[j])
           tmp[k++] = q[i++];
       else
       { 	
           tmp[k++] = q[j++]； 			//如果q[i] > q[j] ,满足逆序对的定义
          	res += mid - i + 1;			//那么从i 到 mid 的所有数都比 q[j] 要大，加上那么多的数量。
       }