七大排序算法——归并排序

AcWing算法——归并排序

---

---

前言

  上一篇博客我分享了快速排序算法的思路和源代码，同时留了一个问题，快速排序的时间复杂度是多少？现在公布答案：快排的时间复杂度是O(n).今天我给大家分享的是七大排序算法中的第二种——归并排序。

---

一、归并排序的思想是什么？

归并排序算法的核心——分治。
  和快速排序相似，也是分治思维，不过在快排里面分界点x由你自己决定，但是在归并排序里面分界点mid=（l+r)/2;
  思路是确定分界点mid，然后将一个区间从中间一分为2，设置两个变量来存储两个区间向后的偏移情况，i指向第一个区间的第一个位置，j保存第二个区间的第一个位置，然后循环判断条件如果成立的话就比较两个位置的大小，谁小就将谁存进提前准备好的tmp数组里面去，最后完成后将tmp数组里面的数据重新拷贝回原来数组，排序完成。

二、算法图示

1.确定分界点：mid=(l+r)/2;
2.递归排序：left，right
3.双路归并 合二为一

三、算法代码

#include 

using namespace std;

const int N = 1e6 + 10;

int a[N], 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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

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

四、算法详解

1.分界点的确定

  选择整个区间的中点即可。

2.左右区间排序

  我们采用递归的方式，将两个区间一直递归，然后就可以很容易的将我们分成的两个区间排好序，然后我们比较两个区间数据的大小，谁小就将谁先放进去然后后移，最终实现双路归并，合二为一，归并排序完成。

总结

这篇博客涉及归并排序，归并排序总体分为三步：
1.确定分界点
2.递归排序左右区间
3.双路归并 合二为一
  最难的地方在于如果递归排序左右区间，这里采用的递归思想需要好好思考一下，很容易就会出错，同时要注意递归的时机，确定分界点后就要立马开始递归，不可以处理一部分数据后在递归，会出现逻辑错误，欢迎大家对思路进行补充，我们明天见~