观感度：????????????????????
口味：小炒黄牛肉
烹饪工夫：10min
本文已收录在前端食堂同名仓库 Github github.com/Geekhyt，欢迎光临食堂，如果感觉酒菜还算可口，赏个 Star 对食堂老板来说是莫大的激励。
排序算法是面试中的高频考察点，咱们须要熟练掌握。本文整顿了最经典、最罕用的排序算法并且搭配了动图和视频，心愿可能帮忙你更加轻松的拿下它们。
首先，依据排序算法的个性能够分成如下两类：
- 比拟类排序
- 非比拟类排序
顾名思义，比拟类排序是通过元素间的比拟进行排序的，非比拟类则不波及元素之间的比拟操作。
比拟类排序的工夫复杂度不能冲破 O(nlogn)，也被称为 非线性排序。
非比拟类排序的工夫复杂度能够冲破 O(nlogn)，可能以线性的工夫运行，也被称为 线性排序。
如果你还不理解工夫复杂度的话，能够移步我的这篇专栏 JavaScript 算法工夫、空间复杂度剖析。
01 冒泡排序 Bubble Sort
冒泡排序可视化视频
冒泡排序，简略粗犷，一句话解释:
冒泡排序在 每次冒泡操作时会比拟相邻的两个元素，看是否满足大小关系要求，不满足就将它俩调换。始终迭代到不再须要替换，也就是排序实现。
const bubbleSort = function(arr) {
const len = arr.length
if (len < 2) return arr
for (let i = 0; i < len; i++) {for (let j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {const temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}- 工夫复杂度: O(n^2)
- 空间复杂度: O(1)
- 稳固
留神：这里的稳固是指，冒泡排序是稳固的排序算法。
什么是稳固的排序算法呢？
排序算法的稳定性
仅仅用 执行效率 和内存耗费 来判断排序算法的优劣是不够的，针对排序算法，还有一个重要的度量指标，稳定性。
意思是说，如果待排序的序列中存在值相等的元素，通过排序之后，相等元素之间原有的先后顺序不变。
举个????：
比方咱们有一组数据：1，9，2，5，8，9。依照大小排序之后就是 1，2，5，8，9，9。
这组数据中有两个 9，通过某种排序算法排序后，如果两个 9 的前后程序没有扭转，咱们就把这种排序算法称为 稳固的排序算法 。
否则，就是 不稳固的排序算法。
冒泡排序优化
下面的代码还能够进行优化，当某次冒泡操作曾经 没有数据交换时，阐明曾经达到齐全有序，不须要再继续执行后续的冒泡操作了。
const bubbleSort = function(arr) {
const len = arr.length
let flag = false
if (len < 2) return arr
for (let i = 0; i < len; i++) {
flag = false // 提前退出冒泡循环的标记
for (let j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {const temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
flag = true // 示意有数据交换
}
}
if (!flag) break // 没有数据交换，提前退出
}
return arr
}02 插入排序 Insertion Sort
插入排序顾名思义，对于未排序的数据，在已排序的序列中从后往前扫描，找到相应的地位进行插入，放弃已排序序列中元素始终有序。
从 i 等于 1 开始遍历，拿到以后元素 curr，与后面的元素进行比拟。
如果后面的元素大于以后元素，就把后面的元素和以后元素进行替换，一直循环直到未排序序列中元素为空，排序实现。
const insertSort = function(arr) {
const len = arr.length
let curr, prev
for (let i = 1; i < len; i++) {curr = arr[i]
prev = i - 1
while (prev >= 0 && arr[prev] > curr) {arr[prev + 1] = arr[prev]
prev--
}
arr[prev + 1] = curr
}
return arr
}- 工夫复杂度: O(n^2)
- 空间复杂度: O(1)
- 稳固
03 抉择排序 Selection Sort
抉择排序可视化视频
抉择排序和插入排序有些相似，也分已排序序列和未排序序列。
然而抉择排序是 将最小的元素寄存在数组起始地位，再从剩下的未排序的序列中寻找最小的元素，而后将其放到已排序的序列前面。以此类推，直到排序实现。
const selectSort = function(arr) {
const len = arr.length
let temp, minIndex
for (let i = 0; i < len - 1; i++) {
minIndex = i
for (let j = i + 1; j < len; j++) {if (arr[j] <= arr[minIndex]) {minIndex = j}
}
temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
return arr
}- 工夫复杂度: O(n^2)
- 空间复杂度: O(1)
- 不稳固
04 归并排序 Merge Sort
分治法典型利用，分治算法思维很大水平上是基于递归的，也比拟适宜用递归来实现。
处理过程是由下到上的，先解决子问题，而后再合并。
如果感觉本人对递归把握的还不是很透彻的同学，能够移步我的这篇专栏你真的懂递归吗？。
顾名思义，分而治之。个别分为以下三个过程：
- 合成：将原问题分解成一系列子问题。
- 解决：递归求解各个子问题，若子问题足够小，则间接求解。
- 合并：将子问题的后果合并成原问题。
归并排序就是将待排序数组一直二分为规模更小的子问题解决，再将解决好的子问题合并起来，这样整个数组就都有序了。
const mergeSort = function(arr) {const merge = (right, left) => {const result = []
let i = 0, j = 0
while (i < left.length && j < right.length) {if (left[i] < right[j]) {result.push(left[i++])
} else {result.push(right[j++])
}
}
while (i < left.length) {result.push(left[i++])
}
while (j < right.length) {result.push(right[j++])
}
return result
}
const sort = (arr) => {if (arr.length === 1) {return arr}
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, arr.length)
return merge(mergeSort(left), mergeSort(right))
}
return sort(arr)
}- 工夫复杂度: O(nlogn)
- 空间复杂度: O(n)
- 稳固
05 疾速排序 Quick Sort
疾速排序可视化视频
疾速排序也是分治法的利用，处理过程是由上到下的，先分区，而后再解决子问题。
疾速排序通过遍历数组，将待排序元素分隔成独立的两局部，一部分记录的元素均比另一部分的元素小，则能够别离对这两局部记录的元素持续进行排序，直到排序实现。
这就须要从数组中挑选出一个元素作为 基准(pivot)，而后从新排序数列，将元素比基准值小的放到基准后面，比基准值大的放到基准前面。
而后将小于基准值的子数组 (left) 和大于基准值的子数组 (right) 递归地调用 quick 办法，直到排序实现。
const quickSort = function(arr) {const quick = function(arr) {if (arr.length <= 1) return arr
const len = arr.length
const index = Math.floor(len >> 1)
const pivot = arr.splice(index, 1)[0]
const left = []
const right = []
for (let i = 0; i < len; i++) {if (arr[i] > pivot) {right.push(arr[i])
} else if (arr[i] <= pivot) {left.push(arr[i])
}
}
return quick(left).concat([pivot], quick(right))
}
const result = quick(arr)
return result
}- 工夫复杂度: O(nlogn)
- 空间复杂度: O(nlogn)
- 不稳固
06 堆排序 Heap Sort
堆排序相比其余几种排序代码会有些简单，不过没关系，咱们先来看一些前置常识，能够帮忙咱们更好的了解堆排序。
堆排序顾名思义就是要利用堆这种数据结构进行排序。堆是一种非凡的树，满足以下两点就是堆：
- 堆是一个齐全二叉树
- 堆中每一个节点的值都必须大于等于 (或小于等于) 其子树中的每个节点的值
每个节点的值都大于等于子树中每个节点值的堆，叫做 大顶堆 ，每个节点的值都小于等于子树中每个节点值的堆，叫做 小顶堆。
也就是说，大顶堆中，根节点是堆中最大的元素。小顶堆中，根节点是堆中最小的元素。
如果你对树这种数据结构还不是很理解，能够移步我的这篇专栏“树”业有专攻
堆如果用一个数组示意的话，给定一个节点的下标 i (i 从 1 开始)，那么它的父节点肯定为 A[i / 2]，左子节点为 A[2i]，右子节点为 A[2i + 1]。
堆排序蕴含两个过程，建堆和排序。首先构建一个大顶堆，也就是将最大值存储在根节点(i = 1)，每次取大顶堆的根节点与堆的最初一个节点进行替换，此时最大值放入了无效序列的最初一位，并且无效序列减 1，无效堆仍然放弃齐全二叉树的构造，而后进行堆化成为新的大顶堆。反复此操作，直到无效堆的长度为 0，排序实现。
const heapSort = function(arr) {buildHeap(arr, arr.length - 1)
let heapSize = arr.length - 1 // 初始化堆的无效序列长度
for (let i = arr.length - 1; i > 1; i--) {swap(arr, 1, i) // 替换堆顶元素与最初一个无效子元素
heapSize-- // 无效序列长度减 1
heapify(arr, heapSize, 1) // 堆化无效序列
}
return arr
}
// 构建大顶堆
const buildHeap = function(items, heapSize) {
// 从后往前并不是从序列的最初一个元素开始，而是从最初一个非叶子节点开始，这是因为，叶子节点没有子节点，不须要自上而下式堆化。// 最初一个子节点的父节点为 n/2，所以从 n/2 地位节点开始堆化
for (let i = Math.floor(heapSize / 2); i >= 1; i--) {heapify(items, heapSize, i)
}
}
// 堆化
const heapify = function(arr, heapSize, i) {while (true) {
let maxIndex = i
if (2 * i <= heapSize && arr[i] < arr[i * 2]) {maxIndex = i * 2}
if (2 * i + 1 <= heapSize && arr[maxIndex] < arr[i * 2 + 1]) {maxIndex = i * 2 + 1}
if (maxIndex === i) break
swap(arr, i, maxIndex)
i = maxIndex
}
}
// 替换工具函数
const swap = function(arr, i, j) {let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}- 工夫复杂度: O(nlogn)
- 空间复杂度: O(1)
- 不稳固
为了不便你了解和记忆，我将这 6 种排序算法的复杂度和稳定性汇总成表格如下：
本文解说了十大经典排序算法中的 6 种排序算法，这 6 种排序算法是平时开发中比拟常见的，大家务必要熟练掌握。
剩下的希尔排序、计数排序、桶排序、基数排序，如果你感兴趣的话能够戳上面链接进行学习。
站在伟人的肩膀上
- 十大经典排序算法
- 前端进阶算法 9：看完这篇，再也不怕堆排序、Top K、中位数问题面试了
- 《JavaScript 外围原理精讲》若离
- 《数据结构与算法之美》王争
2021 组团刷题打算
- 前端食堂的 LeetCode 题解仓库
年初立了一个 flag，下面这个仓库在 2021 年写满 100 道前端面试高频题解，目前进度曾经实现了 1 / 3。
如果你也筹备刷或者正在刷 LeetCode，无妨退出前端食堂，一起并肩作战，刷个畅快。
❤️爱心三连击
1. 如果你感觉食堂酒菜还合胃口，就点个赞反对下吧，你的 赞是我最大的能源。
2. 关注公众号前端食堂，吃好每一顿饭！
3. 点赞、评论、转发 === 催更！