冒泡排序

比较相邻的元素，如果第一个比第二个大，就交换它们。

思路

• 外层循环控制排序轮数，每轮将一个最大值"冒泡"到右侧
• 内层循环进行相邻元素比较和交换
• 每轮结束后，右侧已排好的元素数量增加
• 优化：内层循环范围为 arr.length - 1 - i，因为右侧 i 个元素已排好

代码

// 冒泡排序
// 比较相邻的元素。如果第一个比第二个大，就交换它们两个。

function bubbleSort(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        for(let j = 0; j < arr.length - 1 - i; j++) {
            // 每一轮把一个最大值冒泡到最右边，所以右边已经排好的元素数量 = i
            if(arr[j] > arr[j + 1]){
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
}

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定