归并排序

1945年由约翰:冯.诺伊曼(John von Neumann)首次提出

执行流程

1. 不断的将当前序列品骏分割成两个子序列，直到不能再分割（序列中只剩下1个元素）
2. 不断的将两个子序列合并成1个有序序列，直到最终只剩下一个有序序列

思路

• 将一个数组归并排序，就是将左边的数组归并，右边的数组归并，然后进行合并，递归下去

• 合并的思路：

  • 创建两个索引分别指向两个数组，
  • 将两个归并的数组都从头开始，
  • 比如发现左边数字比较小，拿出左边数字放入大数组，左边索引右移一位，
  • 发现右边的数字比较小，拿出右边的数字放入大数组，右边索引右移一位
  • 最终两个索引都到最后即可

  难点：
  需要合并的两个数组在同一个数组中，并且是挨在一起，
  解决方法，将左边的数组备份出来

dart代码

class MergeSort<T extends Comparable<T>> extends Sort<T> {
  List<T> leftCopy ;
  @override
  sort() {
    leftCopy = List(list.length>>1);//提前定义一般长度的左边长度
    _sort(0, list.length);
  }

  ///
  /// Author: liyanjun
  /// description:  对 [begin, end) 范围的数据进行归并排序
  ///
  _sort(int begin, int end) {
    if (end - begin < 2) return;
    int mid = (end + begin) >> 1; //找到中间位置
    _sort(begin, mid); //左边归并排序
    _sort(mid, end); //右边归并排序
    _merge(begin, mid, end); //合并
  }

  ///
  /// Author: liyanjun
  /// description: 归并
  ///将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
  _merge(int begin, int mid, int end) {
    int leftCopyIndex = 0; //左边的数组
    int leftCopyLength = mid - begin; //左边数组长度
    int rightIndex = mid; //右边数组索引 基于原数组
    int resultIndex = begin; //覆盖的索引
    for (var i = 0; i < leftCopyLength; i++) {
      leftCopy[i]  = list[begin + i];
    } //复制左边的数组
    while (leftCopyIndex < leftCopyLength) {
      //复制的数组遍历完即可，因为两个都是有序数组
      //如果左边数组元素小于右边数组元素，将右边数组元素放在目标索引 ，反之左边数组放入目标索引
      if (rightIndex < end && cmpElement(list[rightIndex], leftCopy[leftCopyIndex]) < 0) {//考虑稳定性，所以不用等于好
        list[resultIndex] = list[rightIndex];
        rightIndex += 1; //右边数组右移动一位
      } else {
        list[resultIndex] = leftCopy[leftCopyIndex];
        leftCopyIndex += 1; //左边数组右移动一位
      }
      resultIndex += 1; //目标数组索引移动一位
    }
  }


}

执行结果

排序前 ：[20, 12, 6, 20, 17, 14, 13, 4, 19, 10]
排序后 ：[4, 6, 10, 12, 13, 14, 17, 19, 20, 20]
【MergeSort<num>】
耗时：0.002s (2ms)     比较：22    交换：0
-----------------

复杂度分析

归并排序花费的时间

T(n) = 2T(n2) + O(n)
推导过程:

;
;
设

则有
S(1)=O(1)

由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是，属于稳定排序
从代码中不难看出:归并排序的空间复杂度是
用于临时存放左侧数组，是因为递归调用

常见的递推公式和时间复杂度

递推式	时间复杂度