> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/notes/articles/sorting/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

```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;
};
```