排序算法番外 - 冒泡排序
2021伊始，决定攻克一下数据结构与算法。在这里带着可爱的小伙伴们一起成长~
你会发现，现在还是在补大学那会逃掉的课程（😌，想逃是逃不掉的，我们一起撸起袖子就是淦！）
我们慢慢来，每天进步一点点，最终会达到量变到质变的效果的！
接下来进入正题，先来搞一波这个经久不衰的排序算法。针对于前端，笔者重点关注面试中考察度较深的排序算法有以下 5 个。
-
基础排序算法 -
冒泡排序 -
选择排序 -
插入排序 -
进阶排序算法 -
归并排序 -
快速排序
而本文我们先讲一个最最基础的，「冒泡排序」。
来了，来了，列车已进站，请抓紧扶手~
冒泡排序
基本思路分析
冒泡排序的过程，就是从第一个元素开始，「重复比较相邻的两个项」，若第一项比第二项更大，则交换两者的位置；反之不动。每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。
基础版的冒泡思路实现
function bubbleSort(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1; j ++) {
if (arr[j] > arr[j + 1]) {
// 如果当前数值大于后一个数值，则调换顺序
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
基础版的冒泡思路改进
在上面，你会发现其实我们 第 i 次 都会将最大的数字 排在 第len - i 上，意味着之后不需要再去比较 len - i之后的数值， 在这里就值得我们去改进。
function betterBubbleSort(arr) {
const len = arr.length
for (let i = 0; i < len; i ++) {
// 注意这里我们直接避免了重复去比较 len - i 之后已经排好序的数值
for (let j = 0; j < len - i - 1; j ++) {
if (arr[j] > arr[j + 1]) {
// 如果当前数值大于后一个数值，则调换顺序
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
}
最优解法
在这里大家想一下，如果是一个已经排好序的数组，那么我们还需要进行两层遍历么，是不是可以达到O(n)的效率。
这里就针对于这种情况作出最优的解法
function bestBubbleSort(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
// 注意这里我们加了一个标志位
let flag = false
for (let j = 0; j < len - i - 1; j ++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
// 只要有一次交换， 就修改标志位
flag = true
}
}
// 如果一次都没交换，证明是有序数组了，直接返回
if (!flag) return arr
}
return arr
}
标志位可以帮助我们在第一次冒泡的时候就定位到数组是否完全有序，进而节省掉不必要的判断逻辑，将最好情况下的时间复杂度定向优化为 O(n)。
「编码复盘 -- 冒泡排序的时间复杂度」
我们分最好、最坏和平均来看：
-
「最好时间复杂度」：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 「O(n)」 -
「最坏时间复杂度」：它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 「O(n^2)」 -
「平均时间复杂度」：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 「O(n^2)」 即可。
行文至此，愿耐心的你已经将这个冒泡排序已经吃透，恭喜恭喜~