我在理解书中算法概念的同时，尝试将里面以Python编写的代码转换为JavaScript。

二分查找法

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回-1。

/**
 * 二分查找法
 * @param {*[]} list
 * @param {*} item
 * @returns {number}
 */
function binarySearch(list, item) {
  let low = 0;
  let high = list.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2); //
    const guess = list[mid];
    if (guess === item) {
      return mid;
    } else if (guess > item) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}
const my_list = [1, 3, 5, 7, 9];
console.log(binarySearch(my_list, 3)); // 1
console.log(binarySearch(my_list, -1)); // -1

链表

链表是一种非连续、非顺序的存储结构。

/** 单向链表 */
class Node {
  /**
   * 创建一条单向链表
   * @param {*} value - 数据域用于存放数据
   * @param {Node | null} next - 指针域用来连接当前结点和下一节点
   */
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}

选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

/**
 * 找到最小的数字
 * @param {number[]} array
 * @returns {number}
 */
function findSmallest(array) {
  let smallest = array[0];
  let smallest_index = 0;
  for (let index = 0; index < array.length; index += 1) {
    if (array[index] <= smallest) {
      smallest = array[index];
      smallest_index = index;
    }
  }
  return smallest_index;
}
/**
 * 选择排序
 * @param {number[]} array
 * @returns {number[]}
 */
function selectionSort(array) {
  const new_array = [];
  for (let index = 0, length = array.length; index < length; index += 1) {
    const smallest_index = findSmallest(array);
    const [smallest] = array.splice(smallest_index, 1);
    new_array.push(smallest);
  }
  return new_array;
}
console.log(selectionSort([5, 3, 6, 2, 10])); // [2,3,5,6,10]

递归

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。

/**
 * 递归阶乘
 * @param {number} n
 * @returns {number}
 */
function factorial(n) {
  if (n <= 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

/**
 * 递归阶乘 - 尾递归优化
 * @param {number} n
 * @param {number} [total=1]
 * @returns {number}
 */
function factorial2(n, total = 1) {
  if (n <= 1) {
    return total;
  }
  return factorial2(n - 1, n * total);
}

/**
 * 斐波那契数列
 * @param {number} n
 * @returns {number}
 */
function fibonacci(n) {
  if (n <= 2) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}
/**
 * 斐波那契数列 - 尾递归优化
 * @param {number} n
 * @param {number} [ac1=1]
 * @param {number} [ac2=1]
 * @returns {number}
 */
function fibonacci2(n, ac1 = 1, ac2 = 1) {
  if (n <= 2) {
    return ac2;
  } else {
    return fibonacci2(n - 1, ac2, ac1 + ac2);
  }
}

分治

分治是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

/**
 * 求和
 * @param {number[]} array
 * @returns {number}
 */
function sum(array) {
  if (array.length) {
    return array.shift() + sum(array);
  }
  return 0;
}

/**
 * 计算元素个数
 * @param {number[]} array
 * @returns {number}
 */
function count(array) {
  if (array.length) {
    array.pop();
    return 1 + count(array);
  }
  return 0;
}

/**
 * 找出最大的数字
 * @param {number[]} array
 * @returns {number}
 */
function findLargest(array) {
  if (array.length === 2) {
    return Math.max(array[0], array[1]);
  } else if (array.length === 1) {
    return array[0];
  } else {
    const sun_max = findLargest(array.slice(1));
    return Math.max(sun_max, array[0]);
  }
}

快速排序

快速排序的工作原理是通过 分治 的方式来将一个数组排序

1. 选择基准值
2. 将数组分成两个子数组：小于基准值的元素和大于基准值的元素
3. 对这两个子数组进行快速排序

/**
 * 快速排序
 * @param {number[]} array
 * @returns {number[]}
 */
function quickSort(array) {
  if (array.length <= 1) {
    return array;
  } else {
    const pivot = array.shift();
    const less = [];
    const greater = [];
    for (let index = 0; index < array.length; index++) {
      const element = array[index];
      if (element <= pivot) {
        less.push(element);
      } else {
        greater.push(element);
      }
    }
    return quickSort(less).concat(pivot).concat(quickSort(greater));
  }
}

console.log(quickSort([10, 5, 2, 3])); // [2,3,5,10]