Skip to main content

冒泡排序

实现：比较任何两个相邻的项，如果第一个比第二个大，则交换位置。

this.bubbleSort = function (array) {
    let len = array.length;
    for (let i = 0; i < len - 1; i++) { // {2}
        for (let j = 0; j < len - 1; j++) { // {3}
            if (array[j] > array[j+1]) {
                swap(array, j, j+1); // 辅助函数，用于交换两个元素的位置
            }
        }
    }
}
// 实现交换两个元素位置的辅助函数
function swap(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
// 👇 有了ES6还可以更简单
function swap(arr, index1, index2) {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}

冒泡排序的示意图： bubble

改进冒泡排序​

caution

注意: 再👆上面的冒泡排序中，当算法执行外循环的第二轮的时候，数字4和5已经是正确排序的了。尽管如此，在后续比较中，它们还一直在进行着比较，即使这是不必要的

如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较（行{1}）。

this.bubbleSort = function (array) {
    let len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) { // {1} 在这里进行改进
            if (array[j] > array[j+1]) {
                swap(array, j, j+1); // 辅助函数，用于交换两个元素的位置
            }
        }
    }
}

改进后的冒泡排序的示意图： bubble