[算法] 归并排序（自顶向下、自底向上）

思路

先将原数组不断二分成两个部分
再把排好序的两部分向上合并为一个新的有序数组，最终的数组就是有序的
这里隐含着一个数学归纳法的证明
- 二分至最终两个数组只有一个元素时，它们本身就是有序的
- 从i-1层向上合并到 i 层，i 层是有序的
- 所以最终得到的数组是有序的

实现

mergeSort()：供用户调用的主函数
__mergeSort()：二分排序数组（O(logN)）
__merge()：将两个排好序的数组向上合并成一个数组（O(N)）
__merge()的实现：
- 开辟一个临时空间（O(n)）拷贝原数组
- 创建三个指针，i、j 指向临时空间中两个排好序数组的第一个元素，每次比较后将元素放入原数组并后移，原数组中的指针k不断后移
- 如果两个排好序数组有一个先处理完，另一个直接复制元素到原数组
两种实现方式：自顶向下和自底向上

代码

自顶向下

MergeSort.h

 1 #include <iostream>
 2 #include <algorithm>
 3 #include "InsertionSort.h"
 4 
 5 using namespace std;
 6 
 7 template<typename T>
 8 // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
 9 void __merge(T arr[] , int l, int mid, int r){
10     T aux[r-l+1];
11     // 将数组复制一份到aux[] 
12     for( int i = l ; i <= r ; i ++ )
13         aux[i-l] = arr[i];
14     // 初始化，i、j指向左、右半部分的起始索引位置 
15     int i = l, j = mid + 1;
16     for( int k = l ; k <= r ; k ++ ){
17         // 如果左半部分已处理完毕 
18         if( i > mid){
19             arr[k] = aux[j-l];
20             j++; 
21         }
22         // 如果右半部分已处理完毕 
23         else if( j > r){
24             arr[k] = aux[i-l];
25             i ++;
26         }
27         // 左半部分所指元素 < 右半部分所指元素 
28         else if( aux[i-l] < aux[j-l] ){
29             arr[k] = aux[i-l];
30             i ++;
31         }
32         // 左半部分所指元素 >= 右半部分所指元素 
33         else{
34             arr[k] = aux[j-l];
35             j++;
36         }
37     }
38 }
39 
40 // 递归使用归并排序，对arr[l...r]的范围进行排序 
41 template<typename T>
42 void __mergeSort(T arr[] , int l, int r){
43     
44     if( l >= r)
45         return; 
46         
47     int mid = (l+r)/2;
48     __mergeSort(arr,l,mid);
49     __mergeSort(arr,mid+1,r);
50     // 优化，前后两部分有序时不归并 
51     if( arr[mid] > arr[mid+1] )
52         __merge(arr, l, mid, r);     
53 } 
54 
55 template<typename T>
56 void mergeSort(T arr[] , int n){
57     __mergeSort( arr , 0 , n-1 );
58 }

自底向上

1 //自底向上归并，可对链表排序 
2 template<typename T>
3 void mergeSortBU(T arr[], int n){
4     for( int sz = 1 ; sz <= n ; sz += sz )
5         for( int i = 0 ; i + sz < n ; i += sz + sz )
6             // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
7             __merge( arr , i , i + sz - 1 , min(i + sz + sz -1,n-1));             
8 }

应用

求逆序对

总结

速度快
当对空间的要求不高时，非常好用