思想
从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 1 的位置。
image
实现
两种方法原理一样, 只是在选择i值上的策略不同
/*
冒泡排序:
平均时间复杂度:O(n2), 最差时间复杂度:O(n2), 是稳定排序, 需要额外空间O(1)
*/
function buble1(array) {
let temp = 0
let flag = false
for (let i = 0; i < array.length -1; i++) {
for (let j = 0; j < array.length -1 -i; j++) {
if (array[j] > array[j+1]) {
flag = true
temp = array[j+1]
array[j+1] = array[j]
array[j] = temp
}
}
console.log(`方法1的第${i}次排序的结果: ${array}`);
if(!flag) {//优化代码,方法2也可使用
break
}else {
flag = false
}
}
}
function buble2(array) {
let temp = 0
for (let i = array.length -1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (array[j] > array[j+1]) {
temp = array[j+1]
array[j+1] = array[j]
array[j] = temp
}
}
console.log(`方法2的第${i}次排序的结果: ${array}`);
}
}
let array = [3,9,-1,10,20]
buble1(array)
array = [3,9,-1,10,20]
buble2(array)
