今天咱们来说说冒泡排序吧！
废话少说，先把代码给肝出来？
const arr = [9, 5, 6, 3, 2, 7, 1, 8, 4]
function sort(arr) {
let temp = null
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
console.log(sort(arr))
运行结果：
运行结果.png
ok，没问题！
那么，再仔细想想，真的是没有什么问题吗？
emmm，应该是没什么问题啊，结果也是正确的。
好的，那么可不可以进行优化呢？
比如，数组的数据如下：
const arr = [1, 2, 3, 4, 5, 6, 9, 8, 7]
我们在循环语句内随便打印个东西看看总共会运行几次
image.png
数不清了，大家可以自己数数。通过观察其实我们可以发现，有很多地方其实是不需要排序的，因为都是已经排好的了，而且那些地方，不是只运行了一遍，而是每个大循环里都会去运行一遍。。。
ok，现在我们知道了这么一种情况，那么怎么去优化它呢？
其实很简单，每次大循环开始时，我们定义一个变量，默认值为true，用来标识数组是否已经排好序。如果接下来的小循环中有元素交换过位置，我们将这个变量设为false，否则不变。等小循环完后，我们去看看这个变量是否为false，如果为false，是不是说明这一次循环有元素交换过位置，那么我们继续进行下一次大循环；如果为true，是不是说明这一次循环没有元素交换过位置，换言之，所有的元素其实已经是排好序的了，对吗？对啊，没毛病啊！那么我们直接结束所有循环，最后直接返回这个数组就好啦！，废话少说，开始优化走起！
const arr = [1, 2, 3, 4, 5, 6, 9, 8, 7]
function sort(arr) {
let temp = null
for (let i = 0; i < arr.length; i++) {
console.log('大循环')
let isSorted = true // 新代码
for (let j = 0; j < arr.length - 1 - i; j++) {
console.log('小循环')
if (arr[j] > arr[j + 1]) {
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
isSorted = false // 新代码
}
}
// 新代码
if (isSorted) {
break
}
}
return arr
}
console.log(sort(arr))
来看结果：
image.png
是不是智能了很多，ok，那么到这真的就结束了吗？再想想还有没有地方可以优化呢？
我们再看看如下场景
const arr = [5, 4, 3, 2, 1, 6, 7, 8, 9]
结果如下：
image.png
通过观察我们可以发现，这个数组后半部分其实已经排好序了，那么我们还有必要每一次都去对后半部分去进行排序吗？当然不需要！
那么如何来解决这个问题呢？
我们可以在最开始定义两个变量，一个是小循环的初始结束条件arrLength（arr.length - 1），另一个是当前这一次大循环的小循环结束后，最后一次元素交换的前一个数的索引lastChangeIndex（默认为0）。然后在小循环中，将结束条件设为刚刚设置的初始条件，如果有元素交换，则将前一个数的索引赋值给前面定义的索引变量。每一次小循环结束，我们将arrLength = lastChangeIndex就可以啦！让每次小循环在最后一次交换元素结束，就保证了后面已经排好序的数据不需要重复去对比排序啦！
老规矩，上代码！
const arr = [5, 4, 3, 2, 1, 6, 7, 8, 9]
function sort(arr) {
let temp = null,
arrLenth = arr.length - 1, // 新代码
lastChangeIndex = 0 // 新代码
for (let i = 0; i < arr.length; i++) {
console.log('大循环')
let isSorted = true
for (let j = 0; j < arrLenth; j++) {
console.log('小循环')
if (arr[j] > arr[j + 1]) {
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
isSorted = false
lastChangeIndex = j // 新代码
}
}
// 新代码
arrLenth = lastChangeIndex
if (isSorted) {
break
}
}
return arr
}
console.log(sort(arr))
结果如下：
image.png
ok，大功告成！
网友评论