冒泡排序如何优化

数组有序的情况下提前结束

如果在一次循环比较的过程中，没有发生 swap 操作，可以说明该数组是有序的，可以提前跳出循环

for (let i = 0; i < arr.length; i++) {
    let isSorted = true; // 注意这里！
    for (let j = 0; j < arr.length - 1 - i; j++) {
        if (compare(arr[j], arr[j + 1])) {
            exchange(arr, j, j + 1);
            isSorted = false;
        }
    }
    if (isSorted) {//注意这里
        return;
    }
}

数组局部有序的情况下提前结束

function bubbleSortOpt2(array){
    let endPos = array.length - 1; // 记录这一轮循环最后一次发生交换操作的位置

    while(endPos > 0){
        let thisTurnEndPos = endPos; // <== 设置这一轮循环结束的位置

        for(let i = 0; i < thisTurnEndPos; i++){
            if(array[i] > array[i+1]){
                swap(array, i, i+1);

                endPos = i; // <== 设置(更新)最后一次发生了交换操作的位置
            }
        }
        
        // 若这一轮没有发生交换,则证明数组已经有序,直接返回即可
        if(endPos === thisTurnEndPos){ 
            return ;
        }
    }
}