一、什么是冒泡排序
冒泡排序指的是重复从序列一端开始比较相邻两个数字的大小，根据交换两个数字的位置，直到整个序列排列完成；在这个过程中，数字会像冒泡一样，一个个慢慢从初始端移到末端，所以被称为冒泡排序。
排序过程
二、代码实现
封装一个升序冒泡
function sort(arr) {
console.log('对'+arr+'进行升序排列')
// 轮数
for (let i = 1; i < arr.length; i++) {
console.log('_____________________')
console.log('这是第'+i+'轮：')
// 次数
for (let j = 0; j < arr.length - i; j++) {
// 前一个数大于后一个数进行交换
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
console.log(arr[j]+'和'+arr[j + 1]+'交换了')
console.log('结果是'+arr)
}
}
}
return arr
}
console.log(sort([89, 6, 13, 45, 0]))
运行结果
对89,6,13,45,0进行升序排列
_____________________
这是第1轮：
89和6交换了
结果是6,89,13,45,0
89和13交换了
结果是6,13,89,45,0
89和45交换了
结果是6,13,45,89,0
89和0交换了
结果是6,13,45,0,89
_____________________
这是第2轮：
45和0交换了
结果是6,13,0,45,89
_____________________
这是第3轮：
13和0交换了
结果是6,0,13,45,89
_____________________
这是第4轮：
6和0交换了
结果是0,6,13,45,89
[ 0, 6, 13, 45, 89 ]
假设数组长度为9，则需要循环8轮，因为每轮都会确定一个最值，所以每轮相比上一轮会减少一次两两比较的次数
通过分析可以发现一个规律：
- 循环的轮数为数组长度减1
- 每轮比较的次数为数组长度减当前轮数
三、代码优化
可以看出，如果在比较完所有的轮数之前数组已经有序，该方法不会停止，仍然会继续执行，有待优化
function sort(arr) {
if (arr == null || arr.length < 2) {
return arr
}
// 轮数
for (var i = 1; i < arr.length; i++) {
console.log('--------------第'+i+'轮')
let change = false
// 次数
for (let j = 0; j < arr.length - i; j++) {
// 前一个数大于后一个数进行交换
if (arr[j] > arr[j + 1]) {
change = true
console.log(arr[j] + '<==>' + arr[j + 1])
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
console.log('结果为'+arr)
}
}
if (!change) {
break
}
}
console.log('执行了'+i+'轮')
return arr
}
console.log(sort([7, 8, 1, 3, 5, 4, 2, 9, 6]))
运行结果
--------------第1轮
8<==>1
结果为7,1,8,3,5,4,2,9,6
8<==>3
结果为7,1,3,8,5,4,2,9,6
8<==>5
结果为7,1,3,5,8,4,2,9,6
8<==>4
结果为7,1,3,5,4,8,2,9,6
8<==>2
结果为7,1,3,5,4,2,8,9,6
9<==>6
结果为7,1,3,5,4,2,8,6,9
--------------第2轮
7<==>1
结果为1,7,3,5,4,2,8,6,9
7<==>3
结果为1,3,7,5,4,2,8,6,9
7<==>5
结果为1,3,5,7,4,2,8,6,9
7<==>4
结果为1,3,5,4,7,2,8,6,9
7<==>2
结果为1,3,5,4,2,7,8,6,9
8<==>6
结果为1,3,5,4,2,7,6,8,9
--------------第3轮
5<==>4
结果为1,3,4,5,2,7,6,8,9
5<==>2
结果为1,3,4,2,5,7,6,8,9
7<==>6
结果为1,3,4,2,5,6,7,8,9
--------------第4轮
4<==>2
结果为1,3,2,4,5,6,7,8,9
--------------第5轮
3<==>2
结果为1,2,3,4,5,6,7,8,9
--------------第6轮
执行了6轮
结果为：[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
数组长度为9，本应该执行8轮，但是第六轮发现没有进行交换，直接退出循环
文章评论