歸并排序

1945年由約翰:馮.諾伊曼(John von Neumann)首次提出

執(zhí)行流程

不斷的將當(dāng)前序列品駿分割成兩個(gè)子序列，直到不能再分割（序列中只剩下1個(gè)元素）
不斷的將兩個(gè)子序列合并成1個(gè)有序序列，直到最終只剩下一個(gè)有序序列

思路

將一個(gè)數(shù)組歸并排序，就是將左邊的數(shù)組歸并，右邊的數(shù)組歸并，然后進(jìn)行合并，遞歸下去
合并的思路：
- 創(chuàng)建兩個(gè)索引分別指向兩個(gè)數(shù)組，
- 將兩個(gè)歸并的數(shù)組都從頭開始，
- 比如發(fā)現(xiàn)左邊數(shù)字比較小，拿出左邊數(shù)字放入大數(shù)組，左邊索引右移一位，
- 發(fā)現(xiàn)右邊的數(shù)字比較小，拿出右邊的數(shù)字放入大數(shù)組，右邊索引右移一位
- 最終兩個(gè)索引都到最后即可
難點(diǎn)：
需要合并的兩個(gè)數(shù)組在同一個(gè)數(shù)組中，并且是挨在一起，
解決方法，將左邊的數(shù)組備份出來

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) 范圍的數(shù)據(jù)進(jìn)行歸并排序
  ///
  _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) 范圍的序列合并成一個(gè)有序序列
  _merge(int begin, int mid, int end) {
    int leftCopyIndex = 0; //左邊的數(shù)組
    int leftCopyLength = mid - begin; //左邊數(shù)組長度
    int rightIndex = mid; //右邊數(shù)組索引 基于原數(shù)組
    int resultIndex = begin; //覆蓋的索引
    for (var i = 0; i < leftCopyLength; i++) {
      leftCopy[i]  = list[begin + i];
    } //復(fù)制左邊的數(shù)組
    while (leftCopyIndex < leftCopyLength) {
      //復(fù)制的數(shù)組遍歷完即可，因?yàn)閮蓚€(gè)都是有序數(shù)組
      //如果左邊數(shù)組元素小于右邊數(shù)組元素，將右邊數(shù)組元素放在目標(biāo)索引 ，反之左邊數(shù)組放入目標(biāo)索引
      if (rightIndex < end && cmpElement(list[rightIndex], leftCopy[leftCopyIndex]) < 0) {//考慮穩(wěn)定性，所以不用等于好
        list[resultIndex] = list[rightIndex];
        rightIndex += 1; //右邊數(shù)組右移動一位
      } else {
        list[resultIndex] = leftCopy[leftCopyIndex];
        leftCopyIndex += 1; //左邊數(shù)組右移動一位
      }
      resultIndex += 1; //目標(biāo)數(shù)組索引移動一位
    }
  }


}

執(zhí)行結(jié)果

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

復(fù)雜度分析

歸并排序花費(fèi)的時(shí)間

T(n) = 2 $*$ T(n $/$ 2) + O(n)
推導(dǎo)過程:
$\because$
$T(1) = O(1)$ ;
$T(n)/n = T(n/2)/(n/2) + O(1)$ ;
設(shè)
$S(n) = T(n)/n$
則有
S(1)=O(1)
$S(n)= S(n/2)+O(1) = S(n/4)+O(2) = S(n/8)+O(3)=S(n/2^k)+O(k)=S(1)+O(logn)= O(logn)$

$\therefore$
$T(n) = n * S(n) = n*O(logn) = O(nlogn)$

由于歸并排序總是平均分割子序列，所以最好、最壞、平均時(shí)間復(fù)雜度都是 $O(nlogn)$ ，屬于穩(wěn)定排序
從代碼中不難看出:歸并排序的空間復(fù)雜度是 $O(n/2 + logn) = O(n)$
$n/2$ 用于臨時(shí)存放左側(cè)數(shù)組， $logn$ 是因?yàn)檫f歸調(diào)用

常見的遞推公式和時(shí)間復(fù)雜度

遞推式	時(shí)間復(fù)雜度
$T(n) = T(n/2) + O(1)$	$O(logn)$
$T(n) = T(n-1) + O(1)$	$O(n)$
$T(n) = T(n/2) + O(n)$	$O(n)$
$T(n) = 2*T(n/2) + O(1)$	$O(n)$
$T(n) = 2*T(n/2) + O(n)$	$O(nlogn)$
$T(n) = T(n-1) + O(n)$	$O(n^2)$
$T(n) = 2*T(n-1) + O(1)$	$O(2^n )$
$T(n) = 2*T(n-1) + O(n)$	$O(2^n)$