（1）快速排序 quick-sort

快速排序

- 前置知识点：
1. pivot：基准

- 原理
1. 选择一个值为 pivot 基准值
2. 所有小于 pivot 的值，都放在左边
3. 所有大于 pivot 的值，都放在右边
4. 等于 pivot 的值可以放在左边，也可以放在右边，还可以再加一个数组，放中间
5. 不断重复以上步骤，直到所有子集只剩下一个元素为止

- 实现：
const arr = [1, 4, 3, 5, 2]

function quickSort (arr) {

  if (arr.length <= 1) { // 递归结束的条件，因为当len<1时，不需要再继续划分三个组进行比较了
    return arr
  }

  const len = arr.length
  const pivot = Math.floor (Math.random() * len) 
  // 获取随机下标
  // 注意这里不能是 len-1，因为边界值，Math.random是[0, 1)，右边是开区间

  let left = []
  let middle = []
  let right = []
  for (let i = 0; i < len; i++) { // 这里 i < len 或者 i <= len都可以
    if (arr[i] < arr[pivot]) {
      left.push (arr[i])
    } else if (arr[i] > arr[pivot]) {
      right.push (arr[i])
    } else if (arr[i] === arr[pivot]) {
      middle.push (arr[i])
    }
  }

  return quickSort (left).concat(middle, quickSort (right)) // 递归拼接数组
}

const res = quickSort(arr)
console.log(res)

https://juejin.im/post/5966f57051882568b20dc3e1

https://juejin.im/post/5c8532ec6fb9a049a42fdd81#heading-7

选择排序 selection-sort

选择排序 selection-sort

原理：
1. 选取数组第一个元素（min），和余下的（数组Y）元素一一做对比（j），如果 j < min，则互换位置，直到Y循环完毕
2. 除去第一个元素，从剩下的数组中，选取第一个元素（min）和余下的数组（Y）一一做对比，重复以上步骤

代码：
const arr = [1, 4, 3, 2]

function select_sort (arr) {
  for (let i = 0; i < arr.length; i++) { // 循环趟数
    let min = i // 用来标记最小值的位置
    for (let j = i + 1; j < arr.length; j ++) { // 循环后面的数组，因为每一趟都找到了当前趟数组的最小值
      if (arr[j] < arr[min]) { // 依次和每趟的第一个元素做对比
        min = j // 如果比这趟的第一个元素小，就标记，即找到该趟的最小元素
      }
    }
    const temp = arr[i] // 每趟找到最新元素位置后，都和第一个元素交换
    arr[i] = arr[min]
    arr[min] = temp
  }
  return arr
}

const res = select_sort (arr)
console.log (res)

https://juejin.im/post/5c6aaac351882562654abdac#heading-1

https://juejin.im/post/5c98ac16e51d451512498b19

插入排序 insert-sort

插入排序 insert-sort

原理：
1. 将数组看成两个部分，一个有序数组，和一个无序数组
2. 有序数组起始长度为1
3. 每次依次从无序数组取出第一个值，和有序数组的最后一个比较，如果该值小于有序数组最后一个值，最后一个值向后移一位
4. 有序数组是从后往前依次比较的，该循环需要满足的条件是j>=0 && 该项值 < 无序数组拿出来比较的值
5. 当有序数组循环比较完后，j+1的位置就是无序数组中拿出来的值需要插入到有序数组中的位置
6. 重复以上步骤

代码：
const arr = [1, 4, 3, 2]

function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) { // 无序数组拿出来比较的元素次数，即趟数，注意从1开始，即无序中初始有一个元素
    const cache = arr[i] // 缓存该值
    let j = i - 1 // 有序数组末位位置

    while (j >= 0 && arr[j] > cache) { // 从后往前循环有序数组，比cache大就往后移动一位
      arr[j+1] = arr[j]
      j--
    }

    arr[j+1] = cache // 插入的位置就是 j+1
  }
  return arr
}
const res = insert_sort(arr)
console.log(res)

https://juejin.im/post/5cd91ceb6fb9a0325031d1db

https://juejin.im/post/5ab62ec36fb9a028cf326c49

希尔排序 shell sort

希尔排序 shell sort


概念：
1. 希尔排序是插入排序的升级版
2. 希尔排序需要取间隔 gap，（将原数组风格成gap个组，然后对每个组进行插入排序）
3. 总的趟数：就是从原数组的gap位置开始，到元素组的最后位置
4. 总结：
希尔排序是按一定的间隔对数组进行分组，然后在每一个分组中做插入排序，然后逐次缩小间隔，
再在每一个分组中做插入排序，直到间隔为1时，结束整个函数
( 注意：gap的最小值一定要是1，即最后所有元素都只在一个数组内进行插入排序 )


复习一下插入排序：（ 看到了一个交换数组的方便写法 ）
1. 交换数组
  - [[a],  [b]] = [[b], [a]]解构的写法很直观和方便
2. 插入排序的原理：
  - 将原数组划分为两个区间，左边是排好序的数组，右边是未排好序的数组
  - 循环右边的数组，即是要比较的趟数
  - 循环左边的数组，分别和右边每趟数组第第一个元素比较
  - 左边数组从后往前循环，如果该次元素比右边数组的第一个元素大，该元素往后移动一位
  - 左边循环结束时，已经找到右边数组第一个元素需要插入的位置
  - 重复以上步骤
2. 插入排序代码：
const arr = [1, 4, 6, 3, 5, 2]
function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) { // 循环的趟数，即看作是右边的无序数组，从1开始，即左边数组有一个元素
    const temp = arr[i] // 缓存该第一个元素，因为左边数组的元素可能会右移一位
    let j = i - 1
    for (; j >= 0 && arr[j] > temp; j--) { // 左边数组，从后往前比较，大于缓存的值就右移动一位，则插入到该值前面
      arr[j+1] = arr[j] // 右移一位
    }
    arr[j+1] = temp // 条件不成立，即左边数组该值大于了temp，说明位置已经找到了，插入该值后面
  }
  return arr
}
const res = insert_sort(arr)
console.log(res, 'res')




3. 希尔排序代码：
- 其实希尔排序只是在插入排序的基础上，分了若干个组，进行插入排序，在重复以上步骤，直到gap所有循环完
- 区间 gap的取值，一般都是  arr.length / 2
const arr = [1, 4, 6, 3, 5, 2]

function shell_sort(arr) {
  let gap = Math.floor(arr.length / 2) // 随机初始化gap，一般情况都是取中间值
  for (; gap >= 1; gap = Math.floor(gap/2)) { 
  // 每趟插入排序的范围，都缩小一半，直到大于0  （即分成几组）
  // 注意：gap最后一定要是1，因为要整个数组执行插入排序一次
    for (let i = gap; i < arr.length; i++) { 
    // 插入排序，从gap开始
    // 从gap开始，到 gap + gap结束即到 arr.length结束
      const temp = arr[i]
      let j = i - gap
      // 有序数组从i-gap开始递减循环，直到 j >= 0
      for (; j >= 0 && arr[j] > temp; j = j-gap) {
          arr[j + gap] = arr[j]
      }
      arr[j+gap] = temp
// 上面的for循环等价于：
// for(; j >= 0; j = j - gap) {
//   if (arr[j] > temp) {
//       arr[j+gap] = arr[j]
//   } else {
//     break
//   }
// }     
    }
  }
  return arr
}
const res = shell_sort(arr)
console.log(res)

图解 https://www.jianshu.com/p/fe5ccc63d523

https://juejin.im/post/5ab62ec36fb9a028cf326c49#heading-23

归并排序 merge-sort

归并排序 merge-sort

原理：
1. 递归的将数组分隔成两个数组，递归结束条件是数组长度为1
2. 递归的从来个有序数组中取第一个元素，比较大小，合并到一个新的数组中，最后返回

代码：
const arr = [1, 4, 2, 5, 3]

// 分隔递归
function merge_sort (arr) {
  if (arr.length <= 1) return arr // 递归结束的条件是数组长度为 0 或者 1

  let mid = Math.floor(arr.length / 2), // 取中间值分隔数组
    left = arr.slice(0, mid), // 左边数组
    right = arr.slice(mid) // 右边数组

  return merge(merge_sort(left), merge_sort(right)) // 递归
}

// 合并
function merge(left, right) {
  let result = []
  
  // 注意：left 和 right 要么是单个元素的数组，要么就是有序的数组 
  // 所以循环取出两个数组的第一项做比较，小的先进新数组
  // 条件是两个数组都有元素时
  while (left.length && right.length) {
    result.push(left[0] < right[0] ? left.shift() : right.shift())
  }
  // 当一个数组没有元素，而另外一个数组还有元素时，剩下的元素一定比新数组中的元素大
  // 因为上面的while循环中已经比较过了，小的都进新数组result中了
  // 所以下面直接拼接就行
  result = result.concat(left.length ? left : right)
  return result
}

const res = merge_sort(arr)
console.log(res)

https://juejin.im/post/5c9cf808f265da611846c015#heading-15

堆排序

堆排序 heap-sort

前置知识：
1. 二叉树
  - 节点 (i) 的 (左孩子2i)，(右孩子2i+1)   
2. 堆
  - 小根堆 - 比它的左右孩子小
  - 大根堆 - 比它的左右孩子大 
3. 完全二叉树
 - 根节点大于左右孩子节点，只有最后一排的孩子未满，并且左排列

4. 堆排序需要解决的两个问题？
  - 如何从一个无序数组构建成一个堆
    - 从完全二叉树的最后一个非叶子节点进行调整，因为页子节点已经是堆
    - 最后一个叶子节点n，那最后一个非页子节点就是 n/2
    - 具体步骤：
      1. 建立初始完全二叉树：将无序数组直接按顺序写成二叉树样式
      2. 从最后一个非叶子节点开始，往前依次进行调整（最后的叶子节点n, 那么就从 n/2开始）
      3. 如果要排成小根堆，就小的在上面，大根堆相反
  
  - 如何在取走堆顶元素后，调整剩余的元素形成一个新堆
    1. 输出堆顶元素后，以堆中最后一个元素替代之
    2. 然后将根节点值与左右子树的根节点值进行比较，并与其中小者进行交换
    3. 重复上述操作，直至下沉到( 叶子节点 )，将得到新的堆
    - 称这个从堆顶至页子的调整过程为 筛选

// 排序
function heapSort(arr) {
  var arr_length = arr.length
  if (arr_length <= 1) return arr
  // 1. 建最大堆
  // 遍历一半元素就够了
  // 必须从中点开始向左遍历，这样才能保证把最大的元素移动到根节点
  for (var middle = Math.floor(arr_length / 2); middle >= 0; middle--) maxHeapify(arr, middle, arr_length)
  // 2. 排序，遍历所有元素
  for (var j = arr_length; j >= 1; j--) {
    // 2.1. 把最大的根元素与最后一个元素交换
    swap(arr, 0, j - 1)
    // 2.2. 剩余的元素继续建最大堆
    maxHeapify(arr, 0, j - 2)
  }
  return arr
}
// 建最大堆
function maxHeapify(arr, middle_index, length) {
  // 1. 假设父节点位置的值最大
  var largest_index = middle_index
  // 2. 计算左右节点位置
  var left_index = 2 * middle_index + 1,
    right_index = 2 * middle_index + 2
  // 3. 判断父节点是否最大
  // 如果没有超出数组长度，并且子节点比父节点大，那么修改最大节点的索引
  // 左边更大
  if (left_index <= length && arr[left_index] > arr[largest_index]) largest_index = left_index
  // 右边更大
  if (right_index <= length && arr[right_index] > arr[largest_index]) largest_index = right_index
  // 4. 如果 largest_index 发生了更新，那么交换父子位置，递归计算
  if (largest_index !== middle_index) {
    swap(arr, middle_index, largest_index)
    // 因为这时一个较大的元素提到了前面，一个较小的元素移到了后面
    // 小元素的新位置之后可能还有比它更大的，需要递归
    maxHeapify(arr, largest_index, length)
  }
}

https://juejin.im/post/5c9cf808f265da611846c015#heading-9