归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

时间复杂度：最好时间复杂度很最坏时间复杂度都是归并排序 - 图1#card=math&code=O%28N%20%5Clog%20N%29)。

归并排序的思想并不能理解，下面我们通过一个例子直观的看一下归并排序中”分”和”归”的具体过程。假设现在待排序数组为归并排序 - 图2：

归并排序.png

分的过程就是不断的进行分解，直到数组元素只有一个。接下来具体看一下最后一次归并的具体过程，设置两个指针left和right分别指向两个待归并子数组的起始位置，并申请临时数组保存此轮归并的结果；当排序结束后将临时数组元素逐个复制到原始数组即可。了解了归并排序的整体流程后，下面给出实现代码：

  1. // Java实现
  2. public class MergeSort {
  4.     public static void mergeSort(int[] arr) {
  5.         if (arr == null || arr.length < 2) {
  6.             return;
  7.         }
  8.         mergeSort(arr, 0, arr.length - 1);
  9.     }
  11.     public static void mergeSort(int[] arr, int l, int r) {
  12.         // 递归出口，当只有一个元素时返回
  13.         if (l == r) {
  14.             return;
  15.         }
  17.         int mid = l + ((r - l) >> 1);
  18.         // 左半个数组排序
  19.         mergeSort(arr, l, mid);
  20.         // 右半个数组排序
  21.         mergeSort(arr, mid + 1, r);
  22.         // 归并有序数组
  23.         merge(arr, l, mid, r);
  24.     }
  26.     // 归并过程
  27.     // 申请额外的数组，设置两个指针分别指向两个子数组的起始位置
  28.     // 选择两个指针指向的较小元素放入数组，更新指针，直到一个数组访问结束
  29.     // 最后将剩下的元素直接放入额外数组的后面即可
  30.     public static void merge(int[] arr, int l, int m, int r) {
  31.         int[] help = new int[r - l + 1];
  32.         int i = 0;
  33.         int p1 = l;
  34.         int p2 = m + 1;
  35.         while (p1 <= m && p2 <= r) {
  36.             help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  37.         }
  38.         while (p1 <= m) {
  39.             help[i++] = arr[p1++];
  40.         }
  41.         while (p2 <= r) {
  42.             help[i++] = arr[p2++];
  43.         }
  45.         // 最后将额外数组中元素复制到原数组中
  46.         for (i = 0; i < help.length; i++) {
  47.             arr[l + i] = help[i];
  48.         }
  49.     }

下面是Python的简单实现：

  1. class MergeSort:
  2.     def __init__(self, arr):
  3.         self.arr = arr
  5.     def sort(self):
  6.         if len(self.arr) < 2: return
  8.         self.mergeSort(self.arr, 0, len(self.arr) - 1)
  9.         print(self.arr)
  11.     def mergeSort(self, arr, left, right):
  12.         if left == right: return
  14.         middle = left + ((right - left) // 2)
  15.         self.mergeSort(arr, left, middle)
  16.         self.mergeSort(arr, middle + 1, right)
  18.         self.merge(arr, left, middle, right)
  20.     def merge(self, arr, left, middle, right):
  21.         array = []
  22.         p, q = left, middle + 1
  24.         while p <= middle and q <= right:
  25.             if arr[p] < arr[q]:
  26.                 array.append(arr[p])
  27.                 p += 1
  28.             else:
  29.                 array.append(arr[q])
  30.                 q += 1
  32.         while p <= middle:
  33.             array.append(arr[p])
  34.             p += 1
  36.         while q <= right:
  37.             array.append(arr[q])
  38.             q += 1
  40.         for i in range(len(array)):
  41.             self.arr[left + i] = array[i]
  43. if __name__ == "__main__":
  44.     a = [1,8,6,5,7,3]
  45.     MergeSort(a).sort()