冒泡排序如何优化
2021-06-14 本文已影响0人
bestCindy
数组有序的情况下提前结束
如果在一次循环比较的过程中,没有发生 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 ;
}
}
}