为啥要考算法？
算法是通用技能，包含了诸多逻辑和相关的技术点，优秀的算法方案会体现出优秀的逻辑思维和和解决问题的能力。
扎实的算法有助于我们在解决复杂问题时获得更优的解决方案。
算法的实现基于不同的语言有不同的形式，对于JavaScript来说，算法的实现也有很多种不同的方式，本文基于JS最新的ES6语法来实现，各位小伙伴在领略算法魅力的同时也能掌握到ES6的语法。
一、冒泡算法
冒泡算法，闻名而知其意，使用类似于水中气泡自下而上逐渐变大的原理（这个原理要是有不清楚的童鞋，可咨询物理老师压强问题，看看老师会不会把你打出shi来...）来对数组进行排序。
排序规则
每次循环，比较当前位置项与下一个位置项的大小，如果当前项 > 后一项，则交换两者的位置。每次循环比较都能选择出一个最大值，放在末尾，剩余待筛选的比较项就减少一项。
如果数组存在n项，那么需要循环执行筛选的次数为n次
二、冒泡算法代码实现
function bubbleSort ([...arr]) {
for (let i = 0; i < arr.length; i++) {
// 第j和j+1项比较，故j的最大值为 = 最大长度 - 1 - 减去已经执行筛选的轮数i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换数组元素的位置
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
}
}
}
return arr
}
let arr = [4, 3, 2, 1]
// 输出排序结果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 输出原数组
console.log(arr) // [4, 3, 2, 1]
ES6语法结构
函数定义时形参：[...arr]
解构赋值和扩展运算符，为不影响原数组，使用该方式接收原数组元素
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]表达式
利用数组的解构赋值，交换两个位置的值
[a, b] = [b, a]
这样就不必借助于第三个变量来交换值
三、冒泡算法优化
使用上面的方式来实现冒泡算法排序时，时间平均复杂度为O(n^2)，那最坏的情况是什么呢？传入的数组完全是逆序的，即[4, 3, 2, 1]。但是如果传入的数组[1, 2, 3, 4]是完全正序的呢？如果还按该方式，那在执行时是性能浪费的，那该如何优化呢？
优化方案
如果数组是完全顺序的，那就说明在执行一次循环比较时，没有数组元素被交换位置，所以我们来设置一个标志flag，初始化为true，如果存在交换则赋值为false。在一次循环后，如果标志为true，则表示为无交换，已经是完全顺序了，则可以break停止外层循环了。下面我们来看下代码实现。
function bubbleSort ([...arr]) {
for (let i = 0; i < arr.length; i++) {
// 设置标记，标记当前轮筛选时是否有交换位置元素，默认为true，如果有交换设置为false
let flag = true
// 第j和j+1项比较，故j的最大值为 最大长度 - 1 - 减去已经执行筛选的轮数i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换数组元素的位置
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
// 有交换位置，设置标记为false
flag = false
}
}
// 如果当前轮比较时没有交换位置，说明已经排序完成了
if (flag) {
break
}
}
return arr
}
let arr = [1, 2, 3, 4]
// 输出排序结果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 输出原数组
console.log(arr) // [1, 2, 3, 4]
此时在完成排序时，只执行了一次循环，此刻的时间复杂度为O(n)
|
|
收藏
淘帖
踩
