欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JS实现的冒泡排序,快速排序,插入排序算法示例

程序员文章站 2022-07-04 21:47:08
本文实例讲述了js实现的冒泡排序,快速排序,插入排序算法。分享给大家供大家参考,具体如下: 一、冒泡排序 大致分两步: 1、依次对比相邻2个数字,前者比后者大就调换位...

本文实例讲述了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;
}

感兴趣的朋友可以使用在线html/css/javascript代码运行工具http://tools.jb51.net/code/htmljsrun测试上述代码运行效果。

ps:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:

更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结

希望本文所述对大家javascript程序设计有所帮助。