关于前端:前端学数据结构与算法七-从零实现优先队列堆及其应用

前言

数据结构章节临时告一段落，从这一章节开始算法之旅。首先从排序开始，排序作为最根底的算法，一点也不简略，写一个快排、堆排、归并排序在大厂面试中并不常见，或者某些题目就须要应用某些排序的思维来解决，这也就是为什么要学习排序。当然最重要的是学习它的思维，例如快排的 partition 操作，快排和归并排序的分治思维，以及排序的性能优化，又或者 O(n²) 的排序也并非一无是处等。本章将手写五种常见排序算法，它们包含冒泡排序、抉择排序、插入排序、归并排序、疾速排序、(堆排序第七章已介绍)，了解它们的优缺点，从而能在适合的场景应用失当的排序算法。

如何掂量一个排序算法？

排序算法的品种很多，在没对排序有理解时，我曾的天真的认为，间接选出其中一个最快的不就完事了么？然而真实情况会简单一些，因为一个排序能从很多不便来掂量，并不能简略的拿效率说事。

1. 工夫复杂度

这是掂量一个排序算法最直观的感触，咱们平时说某一个排序的复杂度也都是均匀工夫复杂度，但针对排序数据的不同，又会呈现最坏、最好工夫复杂度的状况，所以咱们要搞明确，什么状况是什么复杂度。还有就是排序里常常会用到的操作就是替换地位和赋值，很显著赋值的效率是优于替换地位的，这也须要在复杂度之外思考。

2. 额定的内存

实现这个排序算法，须要开拓额定多少的辅助空间，也就是说能不能在原数组上间接原地排序，这个也是须要掂量的一个因素，毕竟快和省才是数据结构与算法存在的意义。

3. 稳定性

尽管说排序算法最初都是依照升序或排序排列，但雷同的值在排序后，地位的前后关系是否产生了扭转这也是掂量的一个规范。例如 [3, 1(1 号), 2, 1(2 号)] 排序后都是 [1, 1, 2, 3]，但1 号和和 2 号是否在排序之后地位产生了扭转，这个也很重要。因为在实在场景，咱们可能是针对某个对象的某个 key 进行排序，如果它们 key 雷同，稳固的排序算法就能放弃原有的秩序不变。

一、冒泡排序(bubbleSort)

置信大家听的最多的就是冒泡排序，它的实现与原理也的确是最好了解的。还是以图解释冒泡排序的原理：

比拟两个相邻的元素，比拟它们的优先级，将大的元素与小的元素进行替换，通过一轮的比拟之后，最大的元素就会呈现在数组的末端，而后再下轮的比拟范畴中排除末端的元素(曾经排好序)。这样的将一个个优先级最大元素浮进去的过程，就相似冒泡般。代码如下：

const bubbleSort = arr => {for (let i = 0; i < arr.length - 1; i++) { // - 1 依据内层的终止条件，能够缩小一次
    for (let j = 0; j < arr.length - i - 1; j++) {
      // - i 放大范畴 - 1 避免数组越界
      if (arr[j] > arr[j + 1]) { // 相邻比拟
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // 替换
      }
    }
  }
}

以上代码的确能实现一个数组的排序，不过通过上述原理示意图不难发现，其实第三步的时候，数组曾经排好序，第四步如果能不执行的话那就好了，针对这个状况咱们能够退出一个标记位，示意数组是否曾经排好序：

const bubbleSort = arr => {for (let i = 0; i < arr.length - 1; i++) {
    let flag = true // 标记位
    for (let j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        flag = false // 只有有一次相邻替换，阐明数组还没排好序
      }
    }
    if (flag) { // 如果遍历了一遍，都没产生相邻替换，阐明排序实现
      break
    }
  }
}

冒泡排序的毛病

1. 工夫复杂度高，须要进行 O(n²) 的两轮比对。
2. 替换地位的操作太频繁，影响 cpu 执行效率。

冒泡排序的长处

1. 是稳固的排序算法，因为值相等时不会进行替换操作。
2. 原地排序不必开拓额定空间。
3. 最好状况面对曾经排好序的数组，复杂度能降到O(n)。

二、抉择排序(selectSort)

实现的原理是在未排好序的范畴内找到最小的值，而后与该范畴头部元素进行替换，从而实现整个数组的排序。原理如下图所示：

首先暂存头部为min，而后再剩下的范畴内找到真正最小值的下标替换min，内层循环完结后，进行一次替换即可。代码如下:

selectSort = arr => {for (let i = 0; i < arr.length; i++) {
    let min = i // 暂定 i 为最小
    for (let j = i + 1; j < arr.length; j++) {if (arr[min] > arr[j]) { // 找到最小的
        min = j
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]] // 内循环完结替换
  }
}

同样都是 O(n²) 的算法，
但就执行效率来说，抉择排序是要优于冒泡排序的，因为冒泡排序比拟之后就会进行替换操作，而抉择排序则非如此，每次内循环只是找到最小值那项的下标，内循环完结后与数组头部替换，剩下的范畴内仍然如此进行，所以比拟次数尽管不会少，但替换地位的操作次数少了很多，执行效率比冒泡高。还是用图阐明下它的原理：

抉择排序的毛病

1. 工夫复杂度高。
2. 不是稳固的排序算法，因为每次找到最小的值后会进行替换地位的操作。
3. 最坏和最好状况都是 O(n²) 的复杂度。

抉择排序的长处

1. 是一种原地排序算法，与冒泡排序相比，替换地位的操作改为了赋值操作，执行效率会进步。

三、插入排序(insertSort)

它的实现原理也是将数组分为排好序和未排好序两个范畴，每次从未排序好里取出元素，插入到曾经排好序的范畴内，反复这个过程以实现整个数组的排序。原理如下：

插入排序与之前两个不同，它的内循环是递加的，只有它后面的元素大于以后的元素，就与它替换地位。从第四步不难发现，如果它后面曾经是排好序的，那么这次内循环能够间接完结。代码如下：

const insertSort = arr => {for (let i = 1; i < arr.length; i++) { // = 1 为了接下来的 -1
    for (let j = i; j > 0; j--) { // 从 i 开始递加
      if (arr[j] < arr[j - 1]) { // 如果之前的元素大于以后的
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]] // 就替换它们的地位
      } else {break // 否则完结本次循环}
    }
  }
}

因为排序原理是从后往前找，而后找到它应该在的地位，而后插入到那个中央即可，所以咱们齐全能够替换地位的操作改为赋值的操作，能够有这样的一个优化，下图所示：

首先暂存须要排序的元素，让暂存的元素与以后的元素进行比拟找到能够插入的地位，如果地位不对，通过赋值的形式整体向后挪动一位，找到后将暂存的元素赋值到它应该在的地位即可。代码如下：

const insertSort = arr => {for (let i = 1; i < arr.length; i++) {let temp = arr[i] // 暂存
    let j
    for (j = i; j > 0 && temp < arr[j - 1]; j--) { // 将 break 写入条件里
      arr[j] = arr[j - 1] // 整体后移
    }
    arr[j] = temp // 将暂存元素插入到对应的地位
  }
}

插入排序的毛病

1. 工夫复杂度高。

插入排序的长处

1. 有提前终止循环的状况，如果是面对近似有序的数组，效率奇高。
2. 原地排序不占额定空间，没有替换地位的操作执行效率高。
3. 是一种稳固的排序算法。
4. 最好状况能到O(n)，(吊打冒泡排序)。

四、归并排序(mergeSort)

归并排序应用的是算法的分治思维，也就是将一个大的问题合成为一个小问题，当问题合成到足够小时，解决了这个小问题，大的问题也就迎刃而解。

首先将一个数组从中一分为二，而后别离解决两个小数组的排序问题，再解决两个小数组时，如果它们还能合成，又将它们分为更小的数组。直到合成到是单个元素为止，而后将单元素数组归并为一个有序的小数组，接着将两个有序的小数组归并为更大一些的数组。直到最初原来一分为二的两个数组就全副是有序的，将它们归并以实现最终的排序。宏观原理图解如下：

而后从宏观的角度来看下如何归并两个有序数组，如下图所示，当须要归并两个有序数组时，咱们须要借助一个原数组的正本，将其拆分为 A 和B。过程是将归并的后果从新赋值原数组 C 实现。

有三个固定的界线坐标别离为 left/mid/right；以及三个游走的坐标k/i/j。从i 到mid是子数组 A，从mid + 1 到right为子数组 B，归并的过程只须要别离比对两个子数组的值即可，谁的值小就赋值给原数组k 下标的地位，而后游走坐标 +1 即可。

在归并的过程中会有四种状况产生：

1. A[i] > B[j]

此时只须要将 B[j] 的值赋值给 C[k]，j++ 以及 k++ 持续归并下一个元素。

1. A[i] < B[j]

将 A[i] 赋值给 C[k]，i++ 以及 k++ 持续归并下一个元素。

1. i > mid

阐明数组 A 外面所有的元素曾经全副归并实现，只须要把数组 B 里的剩下元素全副赋值给数组 C 即可。因为都是有序数组，所以数组 B 里剩下的全部都是大于 A 数组的元素。

1. j > right

同理阐明数组 B 里全副归并实现，将数组 A 剩下的值全副赋值给数组C。

代码如下：

const mergeSort = arr => {const _mergeSort = (arr, l, r) => {if (l >= r) { // 递归终止条件
      return
    }
    const mid = l + (r - l) / 2 | 0 // 取两头下标，向下取整
    _mergeSort(arr, l, mid)
    _mergeSort(arr, mid + 1, r)
    _merge(arr, l, mid, r)
  }
  _mergeSort(arr, 0, arr.length - 1)
}

function _merge(arr, l, mid, r) {const aux = arr.slice(l, r + 1) // 开拓辅助数组
  let i = l;
  let j = mid + 1;
  for (let k = l; k <= r; k++) {if (i > mid) { // 如果数组 A 越界
      arr[k] = aux[j - l]
      j++
    } else if (j > r) { // 如果数组 B 越界
      arr[k] = aux[i - l]
      i++
    } else if (aux[j - l] >= aux[i - l]) { // 这里必须要加上 =
      arr[k] = aux[i - l] // 当值相等时 A 数组先归并，这样能力保障算法的稳定性
      i++
    } else {arr[k] = aux[j - l]
      j++
    }
  }
}

归并排序的毛病

1. 不是原地排序，须要开拓额定的 O(n) 空间。

归并排序的长处

1. 没有最好最坏工夫复杂度，任何状况下都是O(nlogn)；
2. 是一种稳固的排序算法。

五、疾速排序(quickSort)

排序算法里的明星，工夫复杂度也是货真价实，在所有 O(nlogn) 的排序里速度最快，如 JavaScript 封装的 sort 办法就是采纳的快排思维。

快排的实现还是应用的分治的思维，原理就是以其中一个元素作为分区点，将原数组划分为左右两个局部，让左侧数组的值全副比分区点小，右局部数组的值全副比分区点大，这个操作也叫做 patition。对曾经划分的小数组，持续应用patition 的操作，直到划分为单个元素，不能再进行 patition 操作，整个数组的排序工作实现。还是以图来解释：

还是有两个固定的界线坐标 left 和right，有两个游走坐标 i 和j，i示意的是接下来要遍历的点，j示意小区间的开端，所以 j + 1 也就是大区间的结尾。假如咱们抉择此时数组的第一项作为分区点，那么接下来咱们就要从数组的第二项开始遍历，让剩下的所有项与分区点进行比拟。当 i 指向的点小于分区点时，就让其和 j + 1 的地位进行替换，j++扩大小区间的范畴，否则遍历下一个。当数组全副遍历完时，让 left 和j下标的项替换地位即实现了区间的划分。代码如下：

const quickSort = arr => {const _quickSort = (arr, l, r) => {if (l >= r) { // 递归终止条件
      return
    }
    const p = _partition(arr, l, r) // 返回分区点所在下标
    _quickSort(arr, l, p - 1) // 递归进行左半局部
    _quickSort(arr, p + 1, r) // 递归进行右半局部
  }
  _quickSort(arr, 0, arr.length - 1)
}

function _partition(arr, l, r) {const v = arr[l] // 抉择分区点
  let j = l

  for (let i = l + 1; i <= r; i++) { // 从 l + 1，刨去分区点的地位
    if (v > arr[i]) { // 当分区点大于以后节点时
      [arr[i], arr[j + 1]] = [arr[j + 1], arr[i]] 
      // 让大区间的结尾与以后节点替换
      j++  // 小辨别范畴减少
    }
  }
  [arr[j], arr[l]] = [arr[l], arr[j]] // 最初让分区点回到其所在位置
  return j // 返回其下标，进行接下来的分区操作
}

至此实现了一个最简略的快排就实现了，对于快排这个明星算法，切实有太多值得聊，下一章的一整个章节，咱们将深刻了解这种排序算法的思维及对它的优化。

疾速排序的毛病

1. 不是稳固的排序算法。
2. 分区点的抉择有考究，抉择不过后最坏状况会进化为O(n²)。
3. 须要把待排序的数组一次性读入到内存里。

疾速排序的长处

1. 速度快。
2. 原地排序，只须要占用 O(logn) 的栈空间。

最初

至此，最罕用几个排序算法介绍结束。排序算法能够说是算法的基石，下一章独自聊聊快排。

本章 github 源码