05.26 js笔记二十二之数组排序算法-冒泡，递归，快速，插入技术頭條網

2018-05-26 23:05:15 浮生偷閒

冒泡排序

原理: 让数组中的当前项和后一项进行比较, 如果当前项大于后一项,我们让两者交换位置(小 -> 大)

var ary = [12,13,23,14,16,11]
// 第一轮比较: 
// 12 13 [12,13,23,14,16,11]
// 13 23 [12,13,23,14,16,11]
// 23 14 [12,13,14,23,16,11]
// 23 16 [12,13,14,16,23,11]
// 23 11 [12,13,14,16,11,23]
// 第二轮比较: 
// 12 13 [12,13,14,16,11,23]
// 13 14 [12,13,14,16,11,23]
// 14 16 [12,13,14,16,11,23]
// 16 11 [12,13,14,11,16,23]
// ...
// 每一轮从前到后两两比较,虽然不一定实现最后的排序效果,但是可以把当前最大的放到末尾
// 具体比较轮数: ary.length-1; 数组有多长,我们只需把总长度-1个数分别放在末尾,即可实现最后的排序
// 第一轮比较5次: 一共6个,不需要和自己比较
// 第二轮比较4次: 一共6个,不用和自己比较,也不用和第一轮放在末尾的那个最大值比较
// 第三轮比较3次: 
// ...
// 每一轮比较的次数:
//ary.length-1(不用和自己比较) - 当前已经执行的轮数(执行一轮向末尾放一个最大值,这些值不需要再比较)
// a = 12;
// b = 13;
// a和b交换值
// 借用第三个变量先存储一个值,然后替换
// c = a;
// a = b;
// b = c; 

// 不借用三个变量
// a = a+b; // -> 25
// b = a-b; // -> 12 -> b = 12;
// a = a-b; // -> 13 -> a = 13;
// bubble: 冒泡排序
// @parameter
// ary: [array]需要实现排序的数组
// @return
// [array]排序后的数组(升序)
// by team on 2018/05/16
// 升序
function bubble(ary){
 // 外层循环控制的是比较的轮数
 for (var i = 0; i < ary.length-1; i++) {
 // 内层循环控制每一轮比较的次数
 for (var j = 0; j < ary.length-1-i; j++) {
 // ary[j]: 当前本次拿出来的这一项
 // ary[j+1]: 当前项的后一项
 if (ary[j] > ary[j+1]) {
 // 当前项这一项比后一项还要大,我们让两项交换位置
 var temp = ary[j];
 ary[j] = ary[j+1];
 ary[j + 1] = temp;
 }
 }
 }
 return ary;
}
console.log(bubble(ary))
// 降序
function bubble(ary){
 for (var i = 0; i < ary.length-1; i++) {
 for (var j = 0; j < ary.length-1-i; j++) {
 if (ary[j] < ary[j+1]) {
 var temp = ary[j];
 ary[j] = ary[j+1];
 ary[j + 1] = temp;
 }
 }
 }
 return ary; 

}
console.log(bubble(ary))

递归排序

自己调用自己

// 死递归
function fn(num){
 console.log(num)
 fn()
}
fn(10)
function fn(num){
 console.log(num)
 if(mun === 1){
 return
 }
 fn(num - 1)
}
fn(10)

面试题: 1-100之间, 把所有能被3整除并且能被5整除的获取到,然后累加求和

// 方案一:
var total = null;
for(var i=1;i< 100;i++){
 if(i%3 === 0 && i%5 === 0){
 console.log(i)
 total += i;
 }
}
console.log(total)
// 方案二
function fn(num){
 if(num>100){
 return 0;
 }
 if(num%15 === 0){
 return num + fn(num + 1);
 }
 return fn(num+1) 

}
console.log(fn(1))
function fn(num){
 if(num<1){
 return 1;
 }
 if(num%2 === 0){
 return num * fn(num -1);
 }
 return fn(num -1)
}
var result = fn(10);
console.log(result)

快速排序

先找中间这一项

把剩余项的每一个值和中间项进行比较,比他小的放在左边,比他大的放在右边(新数组)

...

var ary = [12,15,14,13,16,11];
function quick(ary){
 // 如果传递进来的数组只有一项或者是空的,我们则不再继续取中间项拆分
 if(ary.length <= 1){
 return ary;
 }
 // 获取中间项的索引: 把中间项的值获取到,在原有数组中删除中间项
 var centerIndex = Math.floor(ary.length/2),
 // splice返回的是个数组,数组中包含了删除的那个内容
 centerValue = ary.splice(centerIndex,1)[0];
 // 用剩余数组中的每一项和中间项比较,比中间项大的放在右边,比中奖项小的放在左边(左右两边都是新数组) 

 var aryLeft = [],
 aryRight = [];
 for (var i = 0; i < ary.length; i++) {
 var cur = ary[i];
 cur < centerValue?aryLeft.push(cur):aryRight.push(cur);
 }
 return quick(aryLeft).concat(centerValue, quick(aryRight));
}
console.log(quick(ary))

插入排序

var ary = [12,15,14,13,16,11];
function insert(ary){
 // 先抓一张牌(一般都抓第一张)
 var handAry = []; // 存储的是手里已经抓取的牌
 handAry.push(ary[0]);
 // 一次循环抓取后面的牌
 for (var i = 1; i < ary.length; i++) {
 var item = ary[i]; // 本次新抓的这张牌
 // 拿新抓的牌和手里现有的牌比较
 for (var j = handAry.length-1; j >= 0; j--) {
 // handAry[j]: 当前比较的手里的这张牌
 // 新抓的牌比当前比较的这张牌大了,我们把新抓的牌放在他的后面
 if(item>handAry[j]){
 handAry.splice(j+1,0,item);
 break;
 }
 if(j === 0){
 // 新传的牌是最小的,把新抓的牌放在最开始的位置
 handAry.unshift(item);
 }
 }
 }
 return handAry;
}
console.log(insert(ary))