主页 > 教程合集 > Html/css >

JS实现的冒泡排序+快速排序+插入排序算法的方法

时间:2019-09-28 阅读:0

本文实例讲述了JS实现的冒泡排序,快速排序,插入排序算法。分享给大家供大家参考,具体如下:

JS实现的冒泡排序+快速排序+插入排序算法的方法

一、冒泡排序

大致分两步:

1、依次对比相邻2个数字,前者比后者大就调换位置

2、重复第一步操作,直到所有数字都按顺序排列


function bubbleSort(arr){
    for(var i=1; i<arr.length; i++){
      for(var j=0; j<arr.length-i; j++){
        if(arr[j]>arr[j+1]){
          arr[j]=[arr[j+1],arr[j+1]=arr[j]][0];
        }
      }
    }
    return arr;
}
 

二、快速排序

大致分三步:

1、找基准(一般是以中间项为基准)

2、遍历数组,小于基准的放在left,大于基准的放在right

3、递归


function quickSort(arr){
      //如果数组<=1,则直接返回
      if(arr.length<=1){return arr;}
      var pivotIndex=Math.floor(arr.length/2);
      //找基准,并把基准从原数组删除
      var pivot=arr.splice(pivotIndex,1)[0];
      //定义左右数组
      var left=[], right=[];
      //比基准小的放在left,比基准大的放在right
      for(var i=0;i<arr.length;i++){
        if(arr[i]<=pivot){
          left.push(arr[i]);
        }else{
          right.push(arr[i]);
        }
      }
      //递归
      return quickSort(left).concat(pivot, quickSort(right));
}
 

三、插入排序(对于少量元素比较有效)

原理:像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的

位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,如图2-1所示。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。

JS实现的冒泡排序+快速排序+插入排序算法的方法

手上的牌是有序数列,桌子上的牌是无序数列。


function insertSort(arr){
    //从第二个数开始,依次插入
    for(var i=1; i<arr.length; i++){
      //判断目标元素是否小于前一个元素
      if(arr[i]<arr[i-1]){
        var current=arr[i];
        var j=i-1;
        //从有序数列从后往前对比,如果目标元素小于与之对比的当前元素,当前元素位置往后挪一位
        while(j>=0 && current<arr[j]) {
          arr[j+1]=arr[j];
          j--;
        }
        //插入
        arr[j+1]=current;
      }
    }
    return arr;
}
 

插入排序另一种写法(个人感觉还是这种效率快)


function insertSort(arr) {
    for(let i=1; i<arr.length; i++) {
        if(arr[i] < arr[0]) {
            arr.unshift(arr.splice(i,1)[0]);
        }else {
            for(let j=i-1; j>=0; j--) {
                if(arr[i] > arr[j]) {
                    let current = arr.splice(i,1)[0];
                    arr.splice(j+1,0,current);
                    break;
                }
            }
        }
    }
    return arr;
}

本站所有资源均在Resource资源站有分享,你可以点击 >>> Resource 进入资源站自助提取,也可以扫描以下店铺二维码直接选购,自动极速发货

余斗微信二维码

扫描微信加好友咨询
了解更多

余斗淘宝店铺二维码

淘宝扫描二维码购买
自动发货

余斗余斗
  • 版权声明:原创文章由发表在Html/css分类下,2019-09-28最后更新,转载注明出处。

相关推荐

返回顶部