排序之冒泡排序

排序之冒泡排序

文章目录

冒泡排序

1 动画2 思想3 解法4 分析

时间复杂度（优化前）稳定性 参考资料

冒泡排序 1 动画

2 思想

（1）对数组进行遍历，相邻两数两两比较，较大者放右边，这样子一趟遍历最大的数就到了数组最右边；

（2）继续以上 *** 作，直至排序完毕。

3 解法

// 冒泡排序(已优化)：如果本次没有元素交换，代表排序已完成
const bubbleSort = arr => {
    const length = arr.length
    if (length <= 1) return
    // 外层迭代排序的轮次，i < length -1 是因为只需要比较 length-1 次就排好了
    for (let i = 0; i < length - 1; i++) {
        let hasChange = false // 提前退出冒泡循环的标志位
        // 内层直接比较相邻两两的大小，迭代次数为未排序数-1(与后一个数进行比较)
        for (let j = 0; j < length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp

                hasChange = true // 表示有元素交换
            }
        }

        // 没有交换则代表排序完成，提前退出冒泡循环
        if (!hasChange) break
    }
}

4 分析 时间复杂度（优化前）

最佳情况：O(n)

最差情况：O(n²)

平均情况：O(n²)

稳定性

稳定

参考资料

Javascript 数据结构与算法之美 - 十大经典排序算法汇总

awesome-coding-js