冒泡排序

[wl05]

冒泡排序： 比较两个相邻的项，如果左边比右边大，则交换两者的位置。

1. 冒泡排序实现

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

const arr = [10, 4, 5, 6, 1, 2, 3, 8, 7, 9, 10]
console.log(bubbleSort(arr))

这里我们可以对冒泡排序进行一下改进,我们可以排除掉已经比较过的元素，每一轮排序完成以后我们就认为当前轮次的元素已经排序好了，在其正确的位置，我们可以将其排除掉

2. 改进后的冒泡排序

function modifiedBubbleSort(arr) {
    const {length} = arr
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // const temp = arr[i]
                // arr[i] = arr[j]
                // arr[j] = temp
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return arr
}

我们可以比较一下两者的运行时间

const arr = [10, 4, 5, 6, 1, 2, 3, 8, 7, 9, 10]
console.time('bubbleSort')
// console.log(bubbleSort(arr))
console.timeEnd('bubbleSort')
console.time('modifiedBubbleSort')
// console.log(modifiedBubbleSort(arr))
console.timeEnd('modifiedBubbleSort')

// bubbleSort: 0.096ms
// modifiedBubbleSort: 0.005ms

效果差距还是很明显的

参考资料

1. 十大经典排序算法（动图演示）