Js中数组算法[冒泡排序,快速排序,插入排序]详解

最后更新于:2018-03-24 14:03:02

冒泡排序,快速排序和插入排序是数组最常用的算法,下面是实现思想和代码。

快速排序

实现思想:
  1. 首先在数组中找一个基准点。
  2. 拿基准点和数组中的其他项进行比较,比基准点小的放在左边,比基准点大的,放在右边。
  3. 如此重复,直到左右只为一项时结束

代码:

function quickSort(ary) {
if (ary.length <= 1)return ary;
//取基准点
var val = ary.splice(0, 1)[0], newLeft = [], newRight = [];
//ary数组一项被取出 数组改变
for (var i = 0; i < ary.length; i++) {
val > ary[i] ? newLeft.push(ary[i]) : newRight.push(ary[i]);
}
return quickSort(newLeft).concat([val], quickSort(newRight));
}
var ary = [2, 16, 6, 8, 3, 11];
var res = quickSort(ary);
console.log(res);

冒泡排序

实现思想:
  1. 数组两两比较,如果前面的值大于后面的值就交换位置
  2. 立一个flag来控制循环次数,如果flag为ture,则继续循环,如果为false就结束(防止多余循环)
  3.  如果i代表比较的轮数,那么最多需要比较ary.length-1轮,每轮比较ary.length-1-i次
function bubbleSort(ary) {
   var flag = false;
   for (var i = 0; i < ary.length - 1; i++) {
      for (var k = 0; k < ary.length - 1 - i; k++) {
         if (ary[k] > ary[k + 1]) {
            var temp = ary[k];
            ary[k] = ary[k + 1];
            ary[k + 1] = temp;
            flag = true;
         }
      }
      if (flag) {
         flag = false;
      } else {
         break;
      }
   }
   return ary;
}
var ary = [2, 16, 6, 8, 22, 11];
var res = bubbleSort(ary);
console.log(res);

插入排序

实现思想:
  1. 首先取数组第一项,放到一个新数组中。
  2. 取数组第二项项与之进行比较,小的放左边,大的放右边。
  3. 取数组第三项与第二项比较,大放右,小再与第一项进行比较,小放左,大放右。
  4. 依次类推,直到数组最后一项。
function insertSort(ary) {
   var newAry = [];
   newAry.push(ary[0]);
   //因为取出了第一项,所以重第二项开始循环
   for (var i = 1; i < ary.length; i++) {
      for (var k = newAry.length - 1; k >= 0;) {
         if (ary[i] > newAry[k]) {
            newAry.splice(k + 1, 0, ary[i]);
            break;
         } else {
            k--;
            if (k === -1) {
               newAry.unshift(ary[i]);
            }
         }
      }
   }
   return newAry;
}
var ary = [2, 66, 6, 5, 22, 11];
var res = insertSort(ary);
console.log(res);