归并排序算法

归并排序算法是在分治算法基础上设计出来的一种排序算法，它可以对指定序列完成升序（由小到大）或降序（由大到小）排序，对应的时间复杂度为O(nlogn)。

归并排序算法实现排序的思路是：

• 将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素；
• 所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。

举个简单的例子，使用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 实现升序排序的过程是：

1) 将 {7, 5, 2, 4, 1, 6, 3, 0} 分割成多个子序列，每个子序列中仅包含 1 个元素，分割过程如下所示：

图1：归并排序算法分割序列的过程

整个序列不断地被一分为二，最终被分割成 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 这几个序列。

2) 将 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 以“两两合并”的方式重新整合为一个有序序列，合并的过程如下图所示：

图2：归并排序算法整合所有子序列的过程

归并排序算法的具体实现

对比图 1 和图 2 很容易联想到，归并排序算法可以借助递归的思想实现，对应的伪代码如下：

输入 arr[n]                                // 输入要排序的序列

merge_sort(arr[n] , p , q):                // [p , q] 表示对第 p ~ q 区域内的元素进行归并排序

   if p < q :                             // 对 [p , q] 区域不断采用对半分割的方式，最终将整个区域划分为多个仅包含 1 个元素（p==q）的序列

       mid = ⌊(p+q)/2⌋

       merge_sort(arr , p , mid)

       merge_sort(arr , mid+1 , q)

       merge(arr , p , mid , q)          // 调用实现归并过程的代码模块

merge_sort() 用于将整个序列分割成多个子序列，merge() 用来合并这些子序列，合并的实现方式为：

1. 从 [p, mid] 和 [mid+1, q] 两个区域的元素分别拷贝到 leftarr 和 rightarr 区域。
2. 从 leftarr 和 rightarr 区域中各个取出第一个元素，比较它们的大小；
3. 将较小的元素拷贝到 [p, q] 区域，然后从较小元素所在的区域内取出下一个元素，继续进行比较；
4. 重复执行第 3 步，直至 leftarr 和 rightarr 内的元素全部拷贝到 [p, q] 为止。如果 leftarr 或者 rightarr 有一方为空，则直接将另一方的所有元素依次拷贝到 [p, q] 区域。

对应的伪代码如下：

merge(arr[n] , p , mid , q):                          // 该算法表示将 [p , mid] 和 [mid+1 , q] 做归并操作

   leftnum <- mid - p + 1                            // 统计 [p , mid] 区域内的元素个数

   rightnum <- q - mid                               // 统计 [mid+1 , q] 区域内的元素个数

   leftarr[leftnum] <- arr[p ... mid]                // 分别将两个区域内的元素各自拷贝到另外两个数组中

   rightarr[rightnum] <- arr[mid+1 ... q]

   i <- 1 , j <- 1

   for k <- p to q :             // 从 leftarr 和 rightarr 数组中第 1 个元素开始，比较它们的大小，将较小的元素拷贝到 arr 数组的 [p , q] 区域

       if leftarr[i] ≤ rightarr[j] :

           arr[k] = leftarr[i]

           i <- i+1

       else :

           arr[k] = right[j]

           j <- j+1

结合伪代码，如下是用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 进行升序排序的C语言程序：

1. #include <stdio.h>
2. //实现分割操作的函数
3. void merge_sort(int* arr, int p, int q);
4. //实现归并操作的函数
5. void merge(int* arr, int p, int mid, int q);
6. 
   
7. int main() {
8. int i = 0;
9. int arr[8] = { 7,5,2,4,1,6,3,0 };
10. //对 arr 数组中第 1 至 8 个元素进行归并排序
11. merge_sort(arr, 1, 8);
12. while (i < 8)
13. {
14. printf("%d ", arr[i]);
15.        i++;
16. }
17. return 0;
18. }
19. //实现分割操作的函数，[p,q] 用于指定归并排序的区域范围，
20. void merge_sort(int* arr, int p, int q) {
21. int mid;
22. if (arr == NULL || p > q || p == q) {
23. return ;
24. }
25.    mid = (p + q) / 2;
26. //将 [p,q] 分为[p,mid] 和 [mid+1,q] 区域
27. merge_sort(arr, p, mid);
28. merge_sort(arr, mid + 1, q);
29. //对分好的 [p,mid] 和 [mid,q] 进行归并操作
30. merge(arr, p, mid, q);
31. }
32. //实现归并操作的函数，归并的 2 个区域分别为 [p,mid] 和 [mid+1,q]
33. void merge(int* arr, int p, int mid, int q) {
34. int i,j,k;
35. int leftarr[100], rightarr[100];
36. int numL = mid - p + 1;
37. int numR = q - mid;
38. //将 arr 数组中 [p,mid] 区域内的元素逐一拷贝到 leftarr 数组中
39. for (i = 0; i < numL; i++) {
40.        leftarr[i] = arr[p - 1 + i];
41. }
42. //将 arr 数组中 [mid+1,q] 区域内的元素逐一拷贝到 rightarr 数组中
43.    leftarr[i] = 2147483647;
44. for (i = 0; i < numR; i++) {
45.        rightarr[i] = arr[mid + i];
46. }
47.    rightarr[i] = 2147483647;
48.    i = 0;
49.    j = 0;
50. //逐一比较 leftarr 和 rightarr 中的元素，每次将较小的元素拷贝到 arr 数组中的 [p,q] 区域内
51. for (k = p; k <= q; k++) {
52. if (leftarr[i] <= rightarr[j]) {
53.            arr[k - 1] = leftarr[i];
54.            i++;
55. }
56. else {
57.            arr[k - 1] = rightarr[j];
58.            j++;
59. }
60. }
61. }

如下是用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 进行升序排序的 Java 程序：

1. public class Demo {
2. //实现归并排序算法的分割操作
3. public static void merge_sort(int[] arr, int p, int q) {
4. // 如果数组不存在或者 [p.q] 区域不合理
5. if (arr == null || p >= q) {
6. return;
7. }
8. //对[p,q]区域进行分割
9. int mid = (p + q) / 2;
10. merge_sort(arr, p, mid);
11. merge_sort(arr, mid + 1, q);
12. //对分割的 [p,mid] 和 [mid+1,q] 区域进行归并
13. merge(arr, p, mid, q);
14. }
15. //实现归并排序算法的归并操作
16. public static void merge(int[] arr, int p, int mid, int q) {
17. int numL = mid - p + 1;
18. int numR = q - mid;
19. //创建 2 个数组，分别存储 [p,mid] 和 [mid+1,q]区域内的元素
20. int[] leftarr = new int[numL + 1];
21. int[] rightarr = new int[numR + 1];
22. int i;
23. for (i = 0; i < numL; i++) {
24.            leftarr[i] = arr[p - 1 + i];
25. }
26. //将 leftarr 数组中最后一个元素设置为足够大的数。
27.        leftarr[i] = 2147483647;
28. for (i = 0; i < numR; i++) {
29.            rightarr[i] = arr[mid + i];
30. }
31. //将 rightarr 数组中最后一个元素设置为足够大的数。
32.        rightarr[i] = 2147483647;
33. int j = 0;
34.        i = 0;
35. //对 leftarr 和 rightarr 数组中存储的 2 个区域的元素做归并操作
36. for (int k = p; k <= q; k++) {
37. if (leftarr[i] <= rightarr[j]) {
38.                arr[k - 1] = leftarr[i];
39.                i++;
40. } else {
41.                arr[k - 1] = rightarr[j];
42.                j++;
43. }
44. }
45. }
46. public static void main(String[] args) {
47. int[] arr = new int[] { 7, 5, 2, 4, 1, 6, 3, 0 };
48. //对 arr 数组中第 1 至 8 个元素进行归并排序
49. merge_sort(arr, 1, 8);
50. for (int i : arr) {
51.            System.out.print(i + " ");
52. }
53. }
54. }

如下是用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 进行升序排序的 Python 程序：

1. #实现归并排序算法中的分割操作，[p,q]为指定分割区域
2. def merge_sort(arr,p,q):
3. #列表中没有数据，或者 [p,q]区域不存在
4. if len(arr) == 1 or p >= q:
5. return
6. #对 [p,q] 区域进行分割
7.    mid = int( (p + q) / 2 )
8. merge_sort(arr,p,mid)
9. merge_sort(arr,mid+1,q)
10. #归并 [p,mid] 和 [mid+1,q] 区域
11. merge(arr,p,mid,q)
12. #实现归并排序算法中的归并操作，归并区域为 [p.mid] 和 [mid+1,q]
13. def merge(arr,p,mid,q):
14.    numL = mid - p + 1;
15.    numR = q - mid;
16. #分别将 [p,mid] 和 [mid+1,q] 区域内的元素拷贝到 leftarr 和 rightarr 列表中
17.    leftarr = arr[p-1:p+numL-1]
18.    rightarr = arr[mid:mid+numR]
19. # 2 个列表末尾添加一个足够大的数
20.    leftarr.append(float('inf'))
21.    rightarr.append(float('inf'))
22.    i=0
23.    j=0
24.    k=p
25. #逐个比较 leftarr 和 rightarr 列表中的元素，每次将较小的元素添加到 arr 列表中的 [p,q] 区域内
26. while k <= q:
27. if leftarr[i] <= rightarr[j]:
28.            arr[k-1] = leftarr[i]
29.            i = i + 1
30. else:
31.            arr[k-1] = rightarr[j]
32.            j = j + 1
33.        k = k + 1
34. 
    
35. arr = [7, 5, 2, 4, 1, 6, 3, 0]
36. #对 arr 数组中第 1 至 8 个元素做归并排序操作
37. merge_sort(arr, 1, 8)
38. print(arr)

以上程序的输出结果均为：

0 1 2 3 4 5 6 7