冒泡排序
原理: 让数组中的当前项和后一项进行比较, 如果当前项大于后一项, 我们让两者交换位置 (小 -> 大)
- 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))
来源: http://www.jianshu.com/p/3db91362b0e7