nlog(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
52
53
54
55
56
57
//
// Created by madman on 2017/7/9.
//归并排序
//

#include <iostream>
using namespace std;

//对arr中的[l,m]和[m+1,r]进行归并
void __merge(int arr[], int l, int m, int r){
    int aux[r-l+1];
    for(int i=l;i<=r;i++){
        aux[i-l] = arr[i];
    }

    int i=l, j = m+1;
    for(int k=l;k<=r;k++ ){

        if(i>m){
            arr[k] = aux[j-l];
            j++;
        } else if(j>r){
            arr[k] = aux[i-l];
            i++;
        } else if(aux[i-l]<aux[j-l]){
            arr[k] = aux[i-l];
            i++;
        } else {
            arr[k] = aux[j-l];
            j++;
        }
    }


}

//递归
void __mergeSort(int arr[], int l, int r){
    if(l>=r)return;
    int mid = (r+l)/2;
    __mergeSort(arr, l, mid );
    __mergeSort(arr, mid+1, r);
    __merge(arr, l, mid, r);
}

void mergeSort(int arr[], int n){
    __mergeSort(arr, 0, n-1);
}

int main(){
    int arr[] = {4,1,3,6,7,2,8,22,12,15,21,9,42,90};
    mergeSort(arr, 14);
    for(int i=0;i<14;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

在上面的代码中，给出长度为n的arr数组进行排序。mergeSort方法调用__mergeSort，传入数组，l，r分别代表数组的左右边界，此处l与r为左闭右闭的区间。__mergeSort中，找出l，r的中间点，对[l,mid],[mid+1, r]区间继续划分，直到区间不可分为止，此时调用__merge方法进行归并操作。

进行归并时，由于要对两个区间进行操作，此时在一个数组中并不好进行，所以需要将数组复制一份，来协助归并操作的完成。归并方法的四个参数，代表对arr数组中，[l,m],[m+1, r]区间进行归并，aux数组存放了一份arr中[l,r]区间的值，用以确定两个区间的值应该存放的位置。其中，变量k代表当前需要存放的位置，i指向左边区间比较的位置，j指向右边区间指向的位置。在循环中，判断i和j位置元素的大小，选择小的放到k的位置，同时k++，被选取的元素i，或j往前移动，直到所有元素遍历完毕，此时[l,r]区间元素归并完毕。

当中需要考虑两种情况，在i或j已经超出各自区间范围时，说明超出一方已经归并完毕，则将剩下的一方按序放入。以上过程不断重复，直至排序完毕。

在上述的方法中，对于一个乱序数组，其效率高于插入排序，但对于近乎有序的数组，则不然。观察__mergeSort方法，在进行归并时无论何种情况都进行了归并操作，但由于[l,mid]与[mid+1,r]区间都已有序，所以，如果arr[mid]<=arr[mid+1]的情况，说明两个序列不在需要归并，它们已经有序了，因此可在归并上加上此判断。同时，在进行递归时，不必一直递归至l>=r，在对区间划分到一定程度时，序列区间相对有序，此时可对区间进行插入排序操作，再进行归并，可在一定程度上提高归并排序的速度。

迭代的方式实现

与递归的方式相反，迭代法的实现是自底向上进行递归操作，例如对于一个数组，先两个一组归并，再四个一组归并，再八个一组归并…直到归并完成，其中的归并过程则是一样的，下面列出不一样的部分：

1
2
3
4
5
6
7
8
9
10
11
12
//自底向上的方式，迭代法实现
void mergeSortBU(int arr[], int n){
    /**
     * sz表示归并步长，由于每次进行归并后，两部分合并，所以步长相当于乘2即 sz+=sz
     */
    for(int sz=1; sz<=n;sz+=sz){
        for(int i=0;i+sz<n;i+=sz+sz){
            //对[i,i+sz-1]和[i+sz,i+sz+sz-1]进行归并操作
            __merge(arr, i, i+sz-1, min(i+sz+sz-1, n-1));
        }
    }
}

上述循环中，外层负责步长的递增，内层则按照外层的步长对整个数组进行归并操作。由于每次归并后两部分合并，对于i来说，它的增长也是sz+sz。考虑到边界问题，内循环中i+sz<n保证了归并中左侧部分的存在，对于右侧部分，则判断i+sz+sz-1和n-1的大小，如果已经超过数组范围，则最大应为数组大小即n-1。

迭代的方式没有使用递归，且它没有直接通过数组下标获取元素，因此，该特性使得它能够对链表这样的数据结构进行排序。对于该方式的优化与递归类似，在数组小时使用插入排序，在进行归并操作前，由于两边数组已经有序，如果在它们边界处 arr[i+sz-1]<arr[i+sz]成立的话，就不用再进行归并操作，以此提高效率。

归并排序（维基百科）https://zh.wikipedia.org/wiki/归并排序
归并排序动画演示 https://visualgo.net/zh/sorting