归并排序 - x-note

Search…
归并排序
归并排序（Merge Sort）是一种基于归并操作的排序算法，核心思想是将两个已经排序的序列合并成一个序列。
平均时间复杂度：O(nlog⁡2n)O({n}\log_{2}{n})O(nlog2​n)
​
最好时间复杂度：O(n)O(n)O(n)
​
最坏时间复杂度：O(nlog⁡2n)O({n}\log_{2}{n})O(nlog2​n)
​
空间复杂度：O(n)O(n)O(n)
​
稳定性：稳定
排序方式：非原地（Not-in-place）
Could not load image
归并算法又分为自顶下下（Top-down）和自底向上（Bottom-up）两种实现方式
自顶向下实现
1.申请一大小为俩个已排序序列之和的空间
2.始比较两个序列中的第一个元素，相对较小的元素放入之前申请的空间
3.取出较小元素所在队列的下一个元素，然后与另一队列之前取出的元素进行比较
4.重复步骤 2~3 直到某个队列提前遍历完成
5.将另一序列的所有元素直接放入申请的空间尾部
Could not load image
具体实现：
// 以下 JavaScript 版本的实现利用了基础库 Array 的特有 API
// 并未考虑达到到最优的空间和时间，仅为了体现核心思想
function mergeSortTopDown(arr) {
    function core(arr1, arr2) {
        const rest = [];
        while (arr1.length && arr2.length) {
            rest.push(arr1[0] <= arr2[0] ? arr1.shift() : arr2.shift());
        }
        return rest.concat(arr1.concat(arr2));
    }
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    let mid = parseInt(len / 2);
    return core(mergeSortTopDown(arr.slice(0, mid)), mergeSortTopDown(arr.slice(mid)));
}
自底向上实现
自底向上就是把序列当作是由 n 个长度为 1 的子序列组成的序列，然后以 2 个序列为单元循环来回地合并子序列
1.将长度为 n 的序列拆分成 n 个子序列
2.每两个相邻的子序列进行归并操作，n 个子序列变成了 ceil(n2)ceil(\dfrac{n}{2})ceil(2n​)
 个新的子序列
3.对所有新的子序列，重复步骤 2，知道最终得到一个长度为 n 的子序列
Could not load image
具体实现：
function mergeSort(arr) {
  const len = arr.length;
  if(arr.length < 2){
    return;
  }
​
  for (let step = 1; step < len; step *= 2) {
    for (let i = 0; i < len; i = i + 2 * step) {
      mergeArrays(
        arr, 
        i, 
        Math.min(i + step, len), 
        Math.min(i + 2 * step, len)
      );
    };
  }
​
  //对左右序列进行排序
  function mergeArrays(arr, left, right, end) {
    let n = left,
        m = right;
    const currentSort = [];
​
    for (let j = left; j < end; j++) {
      if ( n < right && ( m >= end || arr[n] < arr[m] )) {
        currentSort.push(arr[n]);
        n++;
      } else {
        currentSort.push(arr[m]);
        m++;
      }
    }
    //     
    currentSort.forEach(function(item, index) { 
      arr[left + index] = item; 
    });
  }
​
  return arr;
}
快速排序
希尔排序
Last modified 3yr ago
Copy link
Outline
自顶向下实现
自底向上实现