window.onload = function() {
var arr = [2,4,9,1,7,3,6,8,5]
// 冒泡排序
bubbleSort(arr)
// 優(yōu)化后的冒泡排序
bubbleSortNew(arr)
}
// 冒泡排序
function bubbleSort(arr) {
var list = [...arr]
// 外層進(jìn)行數(shù)組長度-1輪循環(huán)
for (let i = 0; i < list.length - 1; i++) {
console.log(`第${i}輪`)
// 內(nèi)層每輪進(jìn)行數(shù)組長度-1-第幾輪次循環(huán)比較
for (let j = 0; j < list.length - 1 - i; j++) {
console.log(`第${j}次比較`)
if (list[j] > list[j + 1]) {
// 當(dāng)前一個的值大于后一個的值進(jìn)行交換
swap(list, j, j + 1)
}
}
}
console.log(list) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
// 優(yōu)化后的冒泡排序
function bubbleSortNew(arr) {
console.log('~~~~~~~~~~~~~~~~~~')
var list = [...arr]
// 數(shù)組長度-1 記錄內(nèi)層循環(huán)的第一輪循環(huán)次數(shù)
var num = arr.length - 1
// 記錄外層循環(huán)輪數(shù)(只用來打印日志)
var m = 0
while (true) {
console.log(`第${m}輪`)
m++
// 記錄最后一次交換時,數(shù)值所在的索引
var last = 0
for (let i = 0; i < num; i++) {
console.log(`第${i}次比較`)
if (list[i] > list[i+1]) {
swap(list, i, i + 1)
last = i
}
}
// 將最后一次交換時數(shù)值所在的索引給到num,用于下次循環(huán)的次數(shù)
num = last
// 當(dāng)num為0時說明已經(jīng)結(jié)束,跳出外層循環(huán)
if (num == 0 ) {
break
}
}
console.log(list) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
// 交換兩個值
function swap(arr, i, j) {
var tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
對比以上兩種方式發(fā)現(xiàn)尿贫，優(yōu)化后的冒泡排序的循環(huán)次數(shù)比沒優(yōu)化的少進(jìn)行了3輪外層循環(huán)电媳；
