排序算法之归并排序

一、归并排序（Merge Sort）

归并���序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

1. 基本思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

  2. 实现逻辑

  2.1 迭代法

  ① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

  ② 设定两个指针，最初位置分别为两个已经排序序列的起始位置

  ③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

  ④ 重复步骤③直到某一指针到达序列尾

  ⑤ 将另一序列剩下的所有元素直接复制到合并序列尾

  2.2 递归法

  ① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素

  ② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

  ③ 重复步骤②，直到所有元素排序完毕

  3. 动图演示

  归并排序演示

  具体的我们以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示：

  上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

  4. 复杂度分析

  平均时间复杂度：O(nlogn)

  最佳时间复杂度：O(n)

  最差时间复杂度：O(nlogn)

  空间复杂度：O(n)

  排序方式：In-place

  稳定性：稳定

  不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )

  归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。

  归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。

  5. 代码实现

  5.1 C版本

  迭代法：

  // 归并排序（C-迭代版）int min(int x, int y) {    return x  
  递归法：
   
  // 归并排序（C-递归版）void merge_sort_recursive(int arr[], int reg[], int start, int end) {    if (start >= end)        return;    int len = end - start, mid = (len >> 1) + start;    int start1 = start, end1 = mid;    int start2 = mid + 1, end2 = end;    merge_sort_recursive(arr, reg, start1, end1);    merge_sort_recursive(arr, reg, start2, end2);    int k = start;    while (start1