bubble_sort.md

排序 - 冒泡排序

概念

冒泡排序会比较数组中相邻的两个数字，如果这两个数字不是排好序的话(按要求，升序或者降序)，就将它们位置交换。

算法

1. 从 arr[0] 开始，比较 arr[0] 和 arr[1]，如果 arr[0] > arr[1]，将两者交换位置(升序)，否则什么都不做。
2. 继续比较 arr[1] 和 arr[2]，如果 arr[1] > arr[2]，将两者交换位置。
3. 继续比较，直到数组的最后一个数字，这样一轮下来之后，最大的数字就被移动到了数组的最后一个位置。
4. 回到 arr[0]，重复步骤 1-3。
5. 重复步骤 4 直到数组中的所有数字都排好序。

复杂度

• 时间复杂度：$O(n^2)$，n 是数组长度。简单地想，有两层循环，最坏的情况是所有数字都需要改变位置，也就是原本的数组是反向排序的，而最好的情况就是 $O(n)$。
• 空间复杂度：$O(1)$。

应用

• 不用考虑时间复杂度的时候(时间复杂度是真的很高)。
• 想要简单实现排序的时候(代码是真的很简单)。

代码

JavaScript

const bubbleSort = arr => {
    while (true) {
        let swapped = false;
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // swap
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                // mark
                swapped = true;
            }
        }
        // 没有数字发生交换，说明已经排好序了，结束循环
        if (!swapped) break;
    }
    return arr;
};