8 - 算法

1. 冒泡排序

/*
* 目标：
*   1. 理解冒泡排序思路
*   2. 理解冒泡排序的代码实现
* */
/*
* 冒泡排序的思路：数组的相邻两项互相比较，如果前一项比后一项大，就交换两项的位置。否则什么也不做；这样
每两个比较过一轮后，可以得出本轮的一个最大值。
*
* 冒泡排序研究两个问题：
*   1. 需要比较的轮数；每一轮都会产生一个最大值，所以只需要比 length - 1 轮就可以比完，因为最后一个一
定是最小的
*   2. 每一轮比较的次数：
*     第1轮需要比较 length - 1 - 0 次
*     第2轮需要比较 length - 1 - 1 次（因为前面已经得出一个最大值，第二轮比较的时候不需要在和前面得出
的最大值比较了）
*     第3轮需要比较 length - 1 - 2次 （有2个最大值）
*     第4轮需要比较 length - 1 - 3次
* */
var ary = [5, 4, 3, 2, 1]; // [4, 3, 2, 1, 5];
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;
    }
  }
}
console.log(ary);

2. 递归

/*
* 目标：
*   1. 理解函数递归
*   2. 理解递归语法
*   3. 理解递归终止的意义
*
* */
function oneToTen() {
  var total = 0;
  for (var i = 1; i <= 10; i++) {
    total += i;
  }
  return total;
}
// 递归写法：
function rOneToTen(num) {
  if (num === 10) {
    // 使用递归时一定要考虑清楚何时终止递归
    return 10
  }
  return num + rOneToTen(num + 1)
  // return 1 + rOneToTen(2)
  // return 1 + 2 + rOneToTen(3)
  // return 1 + 2 + 3 + rOneToTen(4)
  // return 1 + 2 + 3 + 4 + rOneToTen(5)
  // return 1 + 2 + 3 + 4 + 5 + rOneToTen(6)
  // return 1 + 2 + 3 + 4 + 5 + 6 + rOneToTen(7)
  // return 1 + 2 + 3 + 4 + 5 + 6 + 7 + rOneToTen(8)
  // return 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + rOneToTen(9)
  // return 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + rOneToTen(10)
  // return 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 // 55
}
console.log(rOneToTen(1));
// 需求：求出1-10中是3的倍数的所有数字之和
function timesOfThree() {
  var total = 0;
  for (var i = 1; i <= 10; i++) {
    if (i % 3 === 0) {
      total += i;
    }
  }
  return total;
}
function rTimesOfThree(num) {
  if (num === 10) {
    return 0
  }
  if (num % 3 === 0) {
    return num + rTimesOfThree(num + 1);
  } else {
    return rTimesOfThree(num + 1)
  }
  // return rTimesOfThree(2)
  // return rTimesOfThree(3)
  // return 3 + rTimesOfThree(4)
  // return 3 + rTimesOfThree(5)
  // return 3 + 6 + rTimesOfThree(7)
  // return 3 + 6 + rTimesOfThree(8)
  // return 3 + 6 + rTimesOfThree(9)
  // return 3 + 6 + 9 + rTimesOfThree(10)
  // return 3 + 6 + 9 + 0 // 18
}
console.log(rTimesOfThree(1));

3. 通过递归数组排序

/*
* 目标：
*   1. 理解快速排序的原理
*   2. 理解递归在快速排序中的应用
* */
var ary = [12, 8, 88, 97, 86, 85];
// left [12, 8, 88, 86, 85] |97| right []
// left [12, 8, 86, 85]   |88| right [] |97| []
// left [12, 8, 85] |86| right [] |88| [] |97| []
// left [] |8| right [12, 85] |86| [] |88| [] |97| []
// [] |8| left [12] |85| right [] |86| [] |88| [] |97| []
// [8, 12, 85, 86, 88, 97]
// 快速排序的原理：声明两个新数组，分别叫做 left 和 right，然后获取数组的中中间项，然后比中间项小的放在 left 中，然后比中间项大的放在 right 中。然后对 left 和 right 进行同样的操作，直到 left 或者 right 只有一项或者为空时，终止这个过程，然后把所有的 left 和 right 以及中间项拼接起来
function quickSort(ary) {
  // !!! 使用递归要注意递归终止的条件，当前数组 ary 剩余一项或者为空时，就要停止递归
  if (ary.length <= 1) {
    return ary;
  }
  // 1. 计算中间项索引
  var midIndex = Math.floor(ary.length / 2);
  // 2. 获取中间项
  var midVal = ary.splice(midIndex, 1)[0];
  // 3. for 循环遍历数组，如果当前项比中间项大就 push 到 right
  var left = [];
  var right = [];
  for (var i = 0; i < ary.length; i++) {
    var cur = ary[i];
    if (cur > midVal) {
      right.push(cur);
    } else {
      left.push(cur);
    }
  }
  return quickSort(left).concat(midVal, quickSort(right))
}
console.log(quickSort(ary));

4. 插入排序

/*
* 插入排序：
*   1. 理解插入排序原理；
*   2. 理解插入排序实现
* */
/*
* 插入排序原理：
*   1. 假定第一项是最小值；
*   2. 从第二项开始倒着和前面的项进行比较
*   3. 如果前面一项比后一项大，则交换位置
* */
var ary = [5, 4, 3, 2, 1];
function insertSort(ary) {
  for (var i = 1; i < ary.length; i++) {
    for (var j = i; j >= 0; j--) {
      if (ary[j - 1] > ary[j]) {
        var temp = ary[j];
        ary[j] = ary[j - 1];
        ary[j - 1] = temp;
      }
    }
  }
  return ary;
}
console.log(insertSort(ary));