一、冒泡排序

  1. 冒泡排序是升序排列，有点像小鱼吐气泡，大的上面，小的下面
  2. 冒泡排序的核心思想是：让数组的当前项和后一项进行比较，如果当前项比后一项大，就交换位置（大的在后面，小的在前面）

代码实现

const bubble = arr => {
  for (let i = 0; i < arr.length - 1; i++){
    for (let j = 0; j < arr.length - 1; j++){
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

冒泡排序的时间复杂度：最坏的情况是：倒序，一共要进行n-1次循环
(n-1)+(n-2)+(n-3)...+1=n*(n-1)/2
=>O(n²)

冒泡排序的空间复杂度：交换元素的时候那个临时变量所占的内存空间，O(n)

二、选择排序

选择排序的思路时：选定第一个索引的位置，然后和后面的元素依次比较，如果后面的元素小于第一个元素的索引，就交换位置，经过一轮比较以后，可以确定第一个位置是最小的

选择排序：第一轮会选出最小的值，第二轮选出第二小的值，依次类推...

首先从数组里边找到最小的元素，并且把最小的元素放在数组的最前面，然后再从剩下的元素中去寻找第二小的值，放在最小元素的后面，直到排序完毕

代码实现

const arr = [20, 10, 4, 5, 8, 31, 0, 50, 1];

const selectionSort = arr => {
  let min, temp;
  // 判断外层比较次数
  for (let i = 0; i < arr.length - 1; i++){
    // 最小值的下标
    min = i;
    // 假设最小值和后面的元素进行比较
    for (let j = i + 1; j < arr.length; j++){
      // 寻找最小的值
      if (arr[j] < arr[min]) {
        min = j; // 将最小元素的下标保存起来
      }
    }
    // 交换位置
    temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
  }
  return arr;
}

console.log(selectionSort(arr));

时间复杂度：O(n²)
空间复杂度：O(n²)

插入排序

插入排序是简单排序（冒泡，选择，插入排序），效率最高的是插入排序
1、从第一个元素开始，这个元素可以认为以及被排序了（下标是1开始，0这个位置默认以及被排序）
2、取出下一个元素，以及排序的元素中，从后面向前遍历
3、如果说这个元素大于新的元素，就将这个元素移到下一个位置
4、重复上一个步骤，直到找到已经排序的元素小于或者等于新元素的位置
5、将新元素插入到这个位置以后，重复上面的步骤

代码实现

const arr = [9, 6, 2, 3, 1, 8];
const inserSort = arr => {
  const handle = [];
  handle.push(arr[0]);
  // 从第二张牌开始，依次抓牌
  for (let i = 1; i < arr.length; i++){
    let A = arr[i]; // 新抓的牌
    for (let j = handle.length - 1; j >= 0; j--){
      // 每一次都要比较
      let B = handle[j];
      // 如果A比B大
      if (A > B) {
        // 从索引n开始，不删除，把插入的数据添加到index的前面，修改原来的数组
        handle.splice(j + 1, 0, A);
        // 插入成功
        break;
      }
      // 直接放到开头，新牌放到最前面
      if (j === 0) {
        handle.unshift(A);
      }
    }
  }
  return handle;
}

console.log(inserSort(arr));

const arr = [9, 6, 2, 3, 1, 8, 20, 5];
const insertSort = arr => {
  let temp = [];

  // 外层循环控制
  for (let i = 0; i < arr.length; i++){
    // 记录选出的元素，放到temp中
    let j = i;
    temp = arr[i];

    // 内层循环，当前值和之前的每个值进行比较，发现有比当前值小的值的话就进行重新赋值
    while (j > 0&&arr[j-1]>temp) {
      arr[j] = arr[j - 1];
      j--;
    }
    // 选出来的j的位置放到temp中
    arr[j] = temp;
  }
  return arr;
}

console.log(insertSort(arr));

希尔排序

希尔排序的本质是一种插入排序，但是它对数组进行了等间隔的分组处理，在每一组中做插入排序。
O(n²)=>O(nlogn)
希尔排序是按一定的间隔对数组进行分组，然后在每一个分组中做插入排序；随后逐次缩小间隔，在每一个分组中进行插入排序，直到间隔等于1，做一次插入排序后结束

const arr = [9, 6, 2, 3, 1, 8, 20, 5];
const shellSort = arr => {
  let gap = Math.floor(arr.length / 2);
  while (gap > 0) {
    // 插入排序
    // 外层循环控制
    for (let i = 0; i < arr.length; i++) {
      // 记录选出的元素，放到temp中
      let j = i;
      temp = arr[i];

      // 内层循环，当前值和之前的每个值进行比较，发现有比当前值小的值的话就进行重新赋值
      while (j > 0 && arr[j - 1] > temp) {
        arr[j] = arr[j - 1];
        j--;
      }
      // 选出来的j的位置放到temp中
      arr[j] = temp;
    }
    // 重新计算间隔
    gap = Math.floor(gap / 2);
  }
  return arr;
}
console.log(shellSort(arr));

归并排序

拆分和归并
分治
思路：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分结合在一起，归并排序的核心思想就排序和合并两个有序数组。
1、将数组拆分成两个数组，然后对数组各自进行排序
2、合并两个已经排序好的数组

代码实现

const arr = [9, 6, 2, 3, 1, 8, 20, 5];
// 拆分
const divide = arr => {
  if (arr.length === 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);

}

// 合并
const simpleMerge = (left, right) => {
  let temp = [];
  if (left[0] <= right[0]) {
    // 比较left的第一位和right第一位谁小，小的放出来到temp数组
    temp.push(left.shift());
  } else {
    temp.push(right.shift());
  }
  return temp.concat(left, right);
}

const merge = (left, right) => {
  let temp = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      // 比较left的第一位和right第一位谁小，小的放出来到temp数组
      temp.push(left.shift());
    } else {
      temp.push(right.shift());
    }
  }
  return temp.concat(left, right);
}

const mergeSort = arr => {
  if (arr.length === 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}
console.log(mergeSort(arr));

六、快速排序

分治法：
    将原本的问题分解成若干个规模更小但解构与原来的问题相似的子问题，递归解决子问题，然后将这些子问题进行合并

快速排序：
1、选择一个元素作为基准（pivot）
所有小于基准的元素，都移动到（基准）左边，所有大于基准的元素都移动到（基准）右边，分区操作结束完毕以后，基准元素所处的问题就是最终排序后的位置
2、对基准的左边和右边的两个子集，不断重复第一步和第二步直到所有的元素只剩一个为止

代码实现

const arr = [9, 6, 2, 3, 1, 8, 20, 5];

const 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 = [];
  arr.map(item => {
    if (item < pivot) {
      left.push(item);
    } else {
      right.push(item);
    }
  })
  return quickSort(left).concat(pivot, quickSort(right)); // 分治
}

console.log(quickSort(arr));