什么是冒泡排序？

冒泡排序的英文名是 Bubble Sort, 是一种最基础的交换排序。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢 浮 到数列的顶端（升序或降序排列）, 就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名 冒泡排序。

算法原理

  1. 比较两个相邻的元素，将值大（或小，根据升序还是降序决定）的元素交换到右边，如果遇到相等的值不进行交换。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数（降序则是最小的数）。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

分析思路

  1. 比较轮数, 是数组的长度减 1, 因为最后一轮只有一个元素, 每一轮决定一个已排序序列
  2. 每一轮的比较次数, 是数组长度减 1, 因为最后一个元素不需要做比较, 每一次比较决定是否更换位置
  3. 比较结果，以升序排序为例，依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面，降序则相反。

举例

数组 [3, 2, 4, 9, 1, 5, 7, 6, 8], 长度为 9，则需要进行 8 轮比较，每一轮又需要进行 8 次比较，每一轮的 8 次比较完之后将决定一个末尾数字是多少。

以升序为例:

第一轮 第 1 次比较，3 跟 2 比较, 3 比 2 大, 所以将 3 跟 2 交换位置，
[3, 2, 4, 9, 1, 5, 7, 6, 8] 变更为 [2, 3, 4, 9, 1, 5, 7, 6, 8]

第一轮 第 2 次比较，3 跟 4 比较, 4 比 3 大, 所以位置不变，
[2, 3, 4, 9, 1, 5, 7, 6, 8] 依然还是 [2, 3, 4, 9, 1, 5, 7, 6, 8]

第一轮 第 3 次比较，4 跟 9 比较, 9 比 4 大, 所以位置不变，
[2, 3, 4, 9, 1, 5, 7, 6, 8] 依然还是 [2, 3, 4, 9, 1, 5, 7, 6, 8]

第一轮 第 4 次比较，9 跟 1 比较, 9 比 1 大, 所以将 9 跟 1 交换位置，
[2, 3, 4, 9, 1, 5, 7, 6, 8] 数组变更为 [2, 3, 4, 1, 9, 5, 7, 6, 8]

第一轮 第 5 次比较，9 跟 5 比较, 9 比 5 大, 所以将 9 跟 5 交换位置，
[2, 3, 4, 1, 9, 5, 7, 6, 8] 数组变更为 [2, 3, 4, 1, 5, 9, 7, 6, 8]

第一轮 第 6 次比较，9 跟 7 比较, 9 比 7 大, 所以将 9 跟 7 交换位置，
[2, 3, 4, 1, 5, 9, 7, 6, 8] 数组变更为 [2, 3, 4, 1, 5, 7, 9, 6, 8]

第一轮 第 7 次比较，9 跟 6 比较, 9 比 6 大, 所以将 9 跟 6 交换位置，
[2, 3, 4, 1, 5, 7, 9, 6, 8] 数组变更为 [2, 3, 4, 1, 5, 7, 6, 9, 8]

第一轮 第 8 次比较，9 跟 8 比较, 9 比 8 大, 所以将 9 跟 8 交换位置，
[2, 3, 4, 1, 5, 7, 6, 9, 8] 数组变更为 [2, 3, 4, 1, 5, 7, 6, 8, 9]

一轮结束，最后一位数字确定就是 9 是最大的，然后开启第二轮的比较，重复上面步骤，找出末位最大数字，直到第 8 轮结束，后面8位数字都排出来之后，剩下在第一位的数字自然就是最小的。

图解

下面举例动图演示第一轮的比较过程

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 *  @title  冒泡排序
 *  @auhor  Liu Kun
 *  @date   2021/08/24
 *  @param  array 需要做排序的源数组
 *  @param  sort 排序方式 true = 升序  false = 降序，默认升序
 *  @return 排序之后的数组
 **/
function bubbleSort (array, sort = true) {
    const length = array.length
    // 每一轮比较
    for(let i = 0; i < length - 1; i ++) {
        // 每一次比较
        for (let j = 0; j < length - 1; j++) {
            // 根据参数判断是做升序比较还是降序比较
            const compare = sort ? array[j] > array[j + 1] : array[j] < array[j + 1]
            // 比较之后决定是否要交换位置, 这里用到 ES 6 解构语法 交换两个变量的值
            if (compare) [array[j], array[j + 1]] = [array[j+ 1], array[j]]
        }
    }
    return array
}

const array = [3, 2, 4, 9, 1, 5, 7, 6, 8];
bubbleSort(array, true)       // [1, 2, 3, 4, 5, 6, 7, 8, 9]
bubbleSort(array, false)      // [9, 8, 7, 6, 5, 4, 3, 2, 1]

应用场景

使用最简单，适用于数据量很小的排序场景，由于数据移动次数较多，不适用于数据量很大的排序场景。

算法稳定性

冒泡排序就是把小（大）的元素往前调或者把大（小）的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

何为稳定排序

待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中 Ri 领先于 Rj（即 i < j）.若在排序后的序列中 Ri 仍然领先于 Rj，则称所用的方法是稳定的。比如数组 [1,1,1,6,4] 中 a[0], a[1], a[2] 的值相等，在排序时不改变其序列，则称所用的方法是稳定的。