• 在线客服

  • 扫描二维码
    下载博学谷APP

  • 扫描二维码
    关注博学谷微信公众号

  • 意见反馈

原创 六种前端排序算法代码演示

发布时间:2020-04-13 10:23:09 浏览 4316 来源:博学谷 作者:照照

    排序算法是前端算法中一个十分经典的算法,因此它也是前端面试中常见的考察重点。如今前端行业火爆,就业市场对前端人才的要求也越来越高,排序算法是每个前端从业者都必须掌握的基础知识。众所周知,排序算法有六种,分别是冒泡排序、选择排序、快速排序、归并排序、基数排序。下面我为大家逐一用代码演示这六大排序算法,感兴趣的朋友一起来看看吧!

     

    前端排序算法

     

    1、冒泡排序

     

    (1)概念

     

    冒泡排序,顾名思义,就像鱼吐泡泡,泡泡越往上越大。第一次循环,开始比较当前元素与下一个元素的大小,如果比下一个元素小或者相等,则不需要交换两个元素的值;若比下一个元素大的话,则交换两个元素的值。然后,遍历整个数组,第一次遍历完之后,相同操作遍历第二遍。

     

    (2)性能

     

    时间复杂度:平均时间复杂度是O(n^2);空间复杂度:由于辅助空间为常数,所以空间复杂度是O(1)

     

    3)代码演示

     

    const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

     

    function bubbleSort(arr){

     

      for(let i = 0; i < arr.length - 1; i++){

     

        for(let j = 0; j < arr.length - i - 1; j++){

     

          if(arr[j] > arr[j + 1]){

     

            swap(arr, j, j+1);

     

          }

     

        }

     

      }

     

      return arr;

     

    }

     

    function swap(arr, i, j){

     

      let temp = arr[i];

     

      arr[i] = arr[j];

     

      arr[j] = temp;

     

    }

     

    console.log(arr);

     

    2、选择排序

     

    1)概念

     

    选择排序,即每次都选择最小的,然后换位置。第一遍,从数组中选出最小的,与第一个元素进行交换;第二遍,从第二个元素开始,找出最小的,与第二个元素进行交换;依次循环,完成排序。

     

    2)性能

     

    时间复杂度:平均时间复杂度是O(n^2),这是一个不稳定的算法,因为每次交换之后,它都改变了后续数组的顺序。空间复杂度:辅助空间是常数,空间复杂度为O(1)

     

    3)代码演示

     

    const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

     

    function swap(arr, i, j){

     

      var temp = arr[i];

     

      arr[i] = arr[j];

     

      arr[j] = temp;

     

    }

     

     

     

    function selectionSort(arr){

     

      for(let i = 0; i < arr.length - 1; i++){

     

        let index = i;

     

        for(let j = i+1; j < arr.length; j++){

     

          if(arr[index] > arr[j]){

     

            index = j;

     

          }

     

        }

     

        swap(arr, i, index);

     

      }

     

      return arr;

     

    }

     

    console.log(selectionSort(arr)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ] 

     

    3、插入排序

     

    (1)概念

     

    插入排序就是将元素插入到已排序好的数组中。首先,循环原数组,然后,将当前位置的元素,插入到之前已排序好的数组中,依次操作。

     

    (2)性能

     

    时间复杂度:平均算法复杂度为O(n^2);空间复杂度:辅助空间为常数,空间复杂度是O(1)

     

    (3)代码演示

     

    const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100, 50 ,112];

     

    function insertSort(arr){

     

      for(let i = 0; i < arr.length; i++){

     

        let temp = arr[i];

     

        for(let j = 0; j < i; j++){

     

          if(temp < arr[j] && j === 0){

     

            arr.splice(i, 1);

     

            arr.unshift(temp);

     

            break;

     

          }else if(temp > arr[j] && temp < arr[j+1] && j < i - 1){

     

            arr.splice(i, 1);

     

            arr.splice(j+1, 0, temp);

     

            break;

     

          }

     

        }

     

      }

     

      return arr;

     

    }

     

    console.log(insertSort(arr));  //[ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]

     

    4、快速排序

     

    (1)概念

     

    快速排序,从它的名字就应该知道它很快,时间复杂度很低,性能很好。它将排序算法的时间复杂度降低到O

     

    (2)性能

     

    时间复杂度:平均时间复杂度O(nlogn),只有在特殊情况下会是O(n^2),不过这种情况非常少;空间复杂度:辅助空间是logn,所以空间复杂度为O

     

    (3)代码演示

     

    const arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47];

     

    function quickSort(arr){

     

      if(arr.length <= 1){

     

        return arr;

     

      }

     

      let temp = arr[0];

     

      const left = [];

     

      const right = [];

     

      for(var i = 1; i < arr.length; i++){

     

        if(arr[i] > temp){

     

          right.push(arr[i]);

     

        }else{

     

          left.push(arr[i]);

     

        }

     

      }

     

      return quickSort(left).concat([temp], quickSort(right));

     

    }

     

    console.log(quickSort(arr));

     

    5、归并排序

     

    (1)概念

     

    归并排序,即将数组分成不同部分,然后注意排序之后,进行合并。首先,将相邻的两个数进行排序,形成n/2对,然后在每两对进行合并,不断重复,直至排序完。

     

    (2)性能

     

    时间复杂度:平均时间复杂度是O;空间复杂度:辅助空间为n,空间复杂度为O(n)

     

    (3)代码演示

     

    //迭代版本

     

    const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

     

    function mergeSort(arr){

     

      const len = arr.length;

     

      for(let seg = 1; seg < len; seg += seg){

     

        let arrB = [];

     

        for(let start = 0; start < len; start += 2*seg){

     

          let row = start, mid = Math.min(start+seg, len), heig = Math.min(start + 2*seg, len);

     

          let start1 = start, end1 = mid;

     

          let start2 = mid, end2 = heig;

     

          while(start1 < end1 && start2 < end2){

     

            arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);

     

          }

     

          while(start1 < end1){

     

            arrB.push(arr[start1++]);

     

          }

     

          while(start2 < end2){

     

            arrB.push(arr[start2++]);

     

          }

     

        }

     

        arr = arrB;

     

      }

     

      return arr;

     

    }

     

    console.log(mergeSort(arr));

     

    6、基数排序

     

    (1)概念

     

    基数排序,就是将数的每一位进行一次排序,最终返回一个正常顺序的数组。首先,比较个位的数字大小,将数组的顺序变成按个位依次递增的,之后再比较十位,再比较百位的,直至最后一位。

     

    (2)性能

     

    时间复杂度:平均时间复杂度O(k*n),最坏的情况是O(n^2)

     

    (3)代码演示

     

    const arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127, 10000];

     

    function radixSort(arr){

     

      let maxNum = Math.max(...arr);

     

      let dis = 0;

     

      const len = arr.length;

     

      const count = new Array(10);

     

      const tmp = new Array(len);

     

      while(maxNum >=1){

     

        maxNum /= 10;

     

        dis++;

     

      }

     

      for(let i = 1, radix = 1; i <= dis; i++){

     

        for(let j = 0; j < 10; j++){

     

          count[j] = 0;

     

        }

     

        for(let j = 0; j < len; j++){

     

          let k = parseInt(arr[j] / radix) % 10;

     

          count[k]++;

     

        }

     

        for(let j = 1; j < 10; j++){

     

          count[j] += count[j - 1];

     

        }

     

        for(let j = len - 1; j >= 0 ; j--){

     

          let k = parseInt(arr[j] / radix) % 10;

     

          tmp[count[k] - 1] = arr[j];

     

          count[k]--;

     

        }

     

        for(let j = 0; j < len; j++){

     

          arr[j] = tmp[j];

     

        }

     

        radix *= 10;

     

      }

     

      return arr;

     

    }

     

    console.log(radixSort(arr));

     

    以上就是六种前端排序算法的代码演示,大家都看明白了吗?排序算法是前端学习中的基础部分,只要大家明白它的原理,再多动手敲敲代码,相信掌握前端排序算法并不困难。如果大家喜欢本篇文章,欢迎关注博学谷资讯栏目,本栏目将每天为大家更新更多的前端资讯。

    申请免费试学名额    

在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!

上一篇: Uni-App入门教程学习路线分享 下一篇: 如何利用CSS3实现响应式项目开发?

相关推荐 更多

热门文章

  • 前端是什么
  • 前端开发的工作职责
  • 前端开发需要会什么?先掌握这三大核心关键技术
  • 前端开发的工作方向有哪些?
  • 简历加分-4步写出HR想要的简历
  • 程序员如何突击面试?两大招带你拿下面试官
  • 程序员面试技巧
  • 架构师的厉害之处竟然是这……
  • 架构师书籍推荐
  • 懂了这些,才能成为架构师
  • 查看更多

扫描二维码,了解更多信息

博学谷二维码