编辑代码

var array = [1, 5, 2, 7, 3, 9, 6]

console.log('== 冒泡排序 ==\n')

console.log(`冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。\n`)

function createRandomArray(size) {
    var arr = []
    for (let i = 0; i < size; i++) {
        arr.push(Math.round(Math.random() * size))
    }
    array = arr
    // return arr
}

function bubbleSort() {
    var len = array.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(j, j + 1)
            }
        }
    }
}

// 位置交换
function swap(ind1, ind2) {
    var aux = array[ind1]
    array[ind1] = array[ind2]
    array[ind2] = aux
}

createRandomArray(8)
console.time('冒泡排序')
bubbleSort()
console.timeEnd('冒泡排序')
console.log(array)

console.log(`\n 分析：
经过一轮外循环后最大数9以排至数组尾部，后续不用再对9进行比较,内层循环范围缩小至0-(n-1-i)\n`)

console.log('\n改进冒泡排序1\n')
function bubbleSort1() {
    var len = array.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(j, j + 1)
            }
        }
    }
}

createRandomArray(8)
console.time('改进冒泡排序1')
bubbleSort1()
console.timeEnd('改进冒泡排序1')
console.log(array)

console.log(`\n 分析：
内层循环次数已经逐次减少，达到优化效果。
仍存在已完成排序效果，空循环现象。即数组已完成排序，但循环仍在继续，这时给内层循环加上是否完成标识，如果完成则退出循环\n`)

console.log('\n改进冒泡排序2\n')
function bubbleSort2(arr) {
    var len = arr.length
    for (let i = 0; i < len; i++) {
        let isSorted = true
        for (let j = 0; j < len - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(j, j + 1)
                isSorted = false
            }
        }
        // 这里解释一下优化原理:
        // 例如数组[3，2，6，7]，第一次执行后为[2,3,6,7],第二次执行时发现并没有进行位置交换
        // 表示数组已经完成排序，此时直接终止外层循环即可,代码循环共执行两次
        // 次优化点较少，并不能大幅缩减代码执行时间
        if (isSorted) {
            break
        }
    }
}
var arr=[6,3,2,4,5,7,8,9,10]
createRandomArray(8)
console.time('改进冒泡排序2')
bubbleSort2(arr)
console.timeEnd('改进冒泡排序2')
console.log(array)


console.log(`\n 分析：
内层循环次数已经逐次减少，达到优化效果。
空循环现象也已经去除
倘若数组结构为[4,3,1,6,7,8,9],我们会发现6，7，8，9本就是正确的排序
在第一轮排序后数组变为[3,1,4,6,7,8,9]有序数列为4,6,7,8,9 个数5 ，远大于n-(n-1-i)有序个数1，后续比较4,6,7,8,9没有交换位置，浪费循环次数
所以记录最后一次交换位置下标index用于控制内层循环次数，舍弃i-1控制
\n因为优化方式只针对特殊数据的数组，效果不大，同上效果
`)

console.log('\n改进冒泡排序3\n')
function bubbleSort3() {
    var len = array.length
    var lastExchangeIndex = 0 // 最后一次交换对象下标
    var inSortLength = len - 1 // 内层循环次数
    for (let i = 0; i < len; i++) {
        let isSorted = true
        for (let j = 0; j < inSortLength; j++) {
            if (array[j] > array[j + 1]) {
                swap(j, j + 1)
                isSorted = false
                lastExchangeIndex = j
            }
        }
        // 核心思想就是内层循环的执行次数为每次代码执行最后交换位置的下标
        inSortLength = lastExchangeIndex

        if (isSorted) {
            break
        }
    }
}

createRandomArray(8)
console.time('改进冒泡排序3')
bubbleSort3()
console.timeEnd('改进冒泡排序3')
console.log(array)