前端面试题每日更新：js冒泡排序及其优化方法

冒泡排序：

bubbleSort.gif

const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

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

    }
    return arr;
}

console.log(bubbleSort(arr));

冒泡排序优化版：

const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function bubbleSort(arr) {
    let len = arr.length;
    let lastExchangeIndex = 0;
    //无序数列的边界，每次比较只需要比到这里为止
    let sortBorder = len - 1;
    if(len >= 1) {
        for(let i = 0;i < len; i++) {
            //有序标记，每一轮的初始是true
            let isSorted = true;
            for(let j = 0;j < sortBorder - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    let temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    //有元素交换，所以不是有序，标记变为false
                    isSorted = false;
                    //把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if(isSorted) { //有序,跳出循环
                break;
            }
        }

    }
    return arr;
}

console.log(bubbleSort(arr));

---

更多前端面试题，请到github查看或参与讨论https://github.com/daily-interview/fe-interview