阿西河

所有教程

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

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      JavaScript 选择排序

      选择排序

      选择排序的基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止。

      在算法实现时,每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小,交换是个比较耗时的操作。其实 我们很容易发现,在还未完全确定当前最小元素之前,这些交换都是无意义的。我们可以通过设置一个变量 min,每一次比较 仅存储较小元素的数组下标,当轮循环结束之后,那这个变量存储的就是当前最小元素的下标,此时再执行交换操作即可。

      代码实现:

      function selectSort(array) {
      
        let length = array.length;
      
        // 如果不是数组或者数组长度小于等于1,直接返回,不需要排序 
        if (!Array.isArray(array) || length <= 1) return;
      
        for (let i = 0; i < length - 1; i++) {
      
          let minIndex = i; // 设置当前循环最小元素索引
      
          for (let j = i + 1; j < length; j++) {
      
            // 如果当前元素比最小元素索引,则更新最小元素索引
            if (array[minIndex] > array[j]) {
              minIndex = j;
            }
          }
      
          // 交换最小元素到当前位置
          // [array[i], array[minIndex]] = [array[minIndex], array[i]];
          swap(array, i, minIndex);
        }
      
        return array;
      }
      
      // 交换数组中两个元素的位置
      function swap(array, left, right) {
        var temp = array[left];
        array[left] = array[right];
        array[right] = temp;
      }
      

      选择排序不管初始序列是否有序,时间复杂度都为 O(n²)。

      选择排序的平均时间复杂度为 O(n²) ,最坏时间复杂度为 O(n²) ,空间复杂度为 O(1) ,不是稳定排序。

      详细资料可以参考: 《图解排序算法(一)》

      更多面试题

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

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

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

      目录
      目录