阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      JavaScript 归并排序

      归并排序

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

      代码实现:

      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) ,是稳定排序。

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

      更多面试题

      如果你想了解更多的前端面试题,可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题,也有一些大公司的面试图,可以让你面试更加顺利。

      面试题
      HTMLCSSJavaScript
      jQueryVue.jsReact
      算法HTTPBabel
      BootStrapElectronGulp
      Node.js前端经验相关前端综合
      Webpack微信小程序-

      这些题库还在更新中,如果你有不错的面试题库欢迎分享给我,我整理后放上来;人人为我,我为人人,互帮互助,共同提高,祝大家都拿到心仪的Offer!

      目录
      目录