2022-09-20算法00
请注意,本文编写于 579 天前,最后修改于 579 天前,其中某些信息可能已经过时。

归并排序

归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素,然后将数组排序合并,最终合并为排序好的数组。

代码实现:

function mergeSort(array) {

  let length = array.length;

  // 如果不是数组或者数组长度小于等于0,直接返回,不需要排序 
  if (!Array.isArray(array) || length === 0) return;

  if (length === 1) {
    return array;
  }

  let mid = parseInt(length >> 1), // 找到中间索引值
    left = array.slice(0, mid), // 截取左半部分
    right = array.slice(mid, length); // 截取右半部分

  return merge(mergeSort(left), mergeSort(right)); // 递归分解后,进行排序合并
}


function merge(leftArray, rightArray) {

  let result = [],
    leftLength = leftArray.length,
    rightLength = rightArray.length,
    il = 0,
    ir = 0;

  // 左右两个数组的元素依次比较,将较小的元素加入结果数组中,直到其中一个数组的元素全部加入完则停止
  while (il < leftLength && ir < rightLength) {
    if (leftArray[il] < rightArray[ir]) {
      result.push(leftArray[il++]);
    } else {
      result.push(rightArray[ir++]);
    }
  }

  // 如果是左边数组还有剩余,则把剩余的元素全部加入到结果数组中。
  while (il < leftLength) {
    result.push(leftArray[il++]);
  }

  // 如果是右边数组还有剩余,则把剩余的元素全部加入到结果数组中。
  while (ir < rightLength) {
    result.push(rightArray[ir++]);
  }

  return result;
}

归并排序将整个排序序列看成一个二叉树进行分解,首先将树分解到每一个子节点,树的每一层都是一个归并排序的过程,每一层归并的时间复杂度为 O(n),因为整个树的高度为 lgn,所以归并排序的时间复杂度不管在什么情况下都为O(nlogn)。

归并排序的空间复杂度取决于递归的深度和用于归并时的临时数组,所以递归的深度为 logn,临时数组的大小为 n,所以归并排序的空间复杂度为 O(n)。

归并排序的平均时间复杂度为 O(nlogn) ,最坏时间复杂度为 O(nlogn) ,空间复杂度为 O(n) ,是稳定排序。

详细资料可以参考: 《图解排序算法(四)之归并排序》 《归并排序的空间复杂度?》

本文作者:前端小毛

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!