归并排序

前言

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

算法思想

该算法采用经典的分治（divide-and-conquer）策略
分治思想：分治法将问题分(divide)成一些小的问题然后递归求解;而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。

图像理解

图来源：cuijiahua


分而治之：
1、整体排序路径

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。
2、治阶段

时空间复杂度

时间复杂度

归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度即 $abs(log2n)$，其中每次合并操作的时间复杂度为 $O(n)$ ,而根据完全二叉树的可以得出它的时间复杂度是 $O(n*log2n)$ 。

空间复杂度

由前面的算法说明可知，算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列，所以为 $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
48
49
50
51
#include <iostream>

using namespace std;

//归并函数(治阶段)
void Merge(int a[], int tmp[], int stare, int mid, int end)
{
    int tmp_index = 0;                              //设置交换数组的下标
    int left_index = stare;                         //设置左部分数组的下标的起始位置
    int right_index = mid + 1;                      //设置右部分数组的下标的起始位置
    while (left_index <= mid && right_index <= end) //只扫一遍，将左边或右边某个数组的值取完为止
        //这个if语句内的内容是可根据题目要求改变的，将<替换为>即可按从大到小的顺序排序
        if (a[left_index] < a[right_index])
            tmp[tmp_index++] = a[left_index++]; //取值小的一边的值，使得交换数组中的值是按大小顺序排列的
        else
            tmp[tmp_index++] = a[right_index++];
    while (left_index <= mid)
        tmp[tmp_index++] = a[left_index++]; //若左边数组没有取完就接着取右边数组的元素
    while (right_index <= end)
        tmp[tmp_index++] = a[right_index++]; //若右边数组没有取完就接着取右边数组剩下的元素
    //上面两个循环只会有一个循环能满足进入循环的条件
    for (int i = 0; i < (end - stare) + 1; i++) //最后将交换数组的值传递给原数组即可，注意原数组传进来范围，只用排相应范围的顺序
        a[stare + i] = tmp[i];
}
//划分函数(分阶段)
void merge(int a[], int stare, int end, int tmp[]) // tmp是Merage中会用到的一个辅助数组，相当于数值交换时的tmp
{
    if (stare < end)
    {                                        //看似是参与递归的条件，其实是递归结束的条件（当开始的下标小于结束的下标的时候就结束了）
        int mid = stare + (end - stare) / 2; //将传进来的数组的部分再进行一分为二的操作
        merge(a, stare, mid, tmp);           //前一半进行递归
        merge(a, mid + 1, end, tmp);         //后一半进行递归
        Merge(a, tmp, stare, mid, end);      //归并操作，将两半进行归并操作，归并到一起
    }
}

void mergesort() // mergesort入口
{
    int a[10] = {15, -2, 13, -2, 46, -2, 45, 123456, 2, 0}; //待排序的数组
    int size = sizeof(a) / sizeof(int);                     //得到数组大小
    int *tmp = (int *)malloc(sizeof(int) * size);           //为辅助数组申请空间
    merge(a, 0, size - 1, tmp);                             //进入划分函数
    free(tmp);                                              //用完辅助数组后马上释放掉它的内存
    for (int i = 0; i < size; i++)
        cout << a[i] << " "; //输出排好序之后的结果
}

int main()
{
    mergesort();
}