常用算法总结

1. 排序

冒泡排序

实现原理：

长度为 n 的数组，每次比较相邻两个数的大小并根据大小来交换位置，这样第一轮就可以选出一个最大或最小的数放到最后。总共经过 n-1 轮可以完成排序。

代码实现：

function bubbleSort (arr) {
  if(arr.length <= 1) {
    return arr
  }
  // 总共进行arr.length - 1轮排序
  for (let i = 0, max = arr.length-1; i < max; i++) {
    // 排序完成标志位，
    // 当没有相邻数据交换时证明排序完成，反之，则证明排序尚未完全结束
    let done = true;

    // 每轮的两两比较只需要进行到 max-i 即可，因为max-i后面的数据都是之前排好的
    for (let j = 0; j < max - i; j++) {
      // 这里是升序排序
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        done = false;
      }
    }

    // 排序完成，提前终止，减少不必要的循环
    if (done) {
      break;
    }
  }
  return arr;
}

快速排序

实现原理：

从数组中选择一个元素作为基准点，遍历数组，将数组所有比基准值小的元素摆放在左边的数组中，而大于基准值的摆放在右边的数组中。每次分割结束以后基准值会插入到中间去。
最后利用递归，将左边的数组和右边的数组再进行一次上述操作。

代码实现：

function quickSort(arr) {
  // 递归终止条件
  if(arr.length <= 1) {
    return arr
  }

  // 获取数组中间的元素下标,将该元素作为基准值
  const pivotIndex = Math.floor(arr.length / 2);
  // 将该基准值从原数组中剪切出来
  const pivot = arr.splice(pivotIndex, 1)[0];

  // 定义两个空数组，分别用于存放小于基准值的元素和大于基准值的元素
  const left = [];
  const right = [];

  // 遍历元素进行数据分组
  for (let i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 递归，对左右两个数组排序，并拼接，得到最终排序好的结果
  return quickSort(left).concat([pivot], quickSort(right));
}

归并排序

实现原理：

递归将数组两两分开直到包含一个元素，然后将数组排序合并，最终合并为排序好的数组。

代码实现：

// 采用自上而下的递归方法
function mergeSort(arr) {
  const len = arr.length;
  if(len <= 1 ) {
    return arr;
  }

  // 获取中间元素下标，并将数组拆分为left部分和right部分
  const middle = Math.floor(len / 2),
  left = arr.slice(0, middle),
  right = arr.slice(middle);

  // 递归实现排序
  return merge(mergeSort(left), mergeSort(right));
}

// 将各自有序的两个数组进行排序合并
function merge(left, right)
{
  const result = [];

  // 比较左右数组的头部元素，将值小的元素添加到result尾部
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  // 只有左数组时，将元素依次添加至result尾部
  while (left.length) {
    result.push(left.shift());
  }

  // 只有右数组时，将元素依次添加至result尾部
  while (right.length) {
    result.push(right.shift());
  }

  // 返回排序后的数组
  return result;
}

2. 递归和循环

阶乘

// 常规递归实现，复杂度O(n) 
function factorial(n) { 
  if(n === 1) return 1; 
  return n * factorial(n-1); 
} 

// 尾递归优化，复杂度O(1) 
function factorial(n, result = 1) { 
  if(n === 1) return result; 
  return factorial(n-1, n * result); 
}

// 递推实现
function factorial(n) {
  let res = 1;
  for (let i = 1; i <= n; i++) {
    res = res * i;
  }
  return res;
}

斐波那契数列

初始前两项为1，后续各项等于前两项之和：

// 常规递归实现
function fibonacci(n) {
  if (n <= 2) {
    return 1
  }

  return fibonacci(n-1) + fibonacci(n-2)
}

// 尾递归优化
function fibonacci(n, prev=1, cur=1) {
  if (n <= 2) {
    return cur
  }
  return fibonacci(n-1, cur, cur+prev )
}

// 递推实现
function fibonacci(n) {
  let cur = 1;
  let next = 1;
  for (let i = 1; i < n; i++) {
    [cur, next] = [next, cur + next]
  }
  return cur;
}

3. 洗牌算法（乱序）

实现原理：

从最后一个元素开始，从数组中随机选出一个位置，交换，直到第一个元素。

function disorder(arr) {
  for(let len=arr.length, i = len-1; i>-1; i--) {
    let random = Math.floor(len * Math.random());
    [arr[i], arr[random]] = [arr[random], arr[i]];
  }
  return arr;
}

4. 全排列

字典序

邻位对换法

循环右移法

递增进位制法

递减进位制法