冒泡排序（Bubble Sort）：是一种简单的排序算法，也是一种稳定的排序算法，但它运行效率也较低。其实现原理是：从左到右依次比较两个相邻的元素，当该对元素顺序不正确时就进行交换，重复此步骤，直到没有任何两个相邻的元素可以交换，就表明完成了排序。

一般情况下，称某个排序算法稳定，指的是当待排序序列中有相同的元素时，它们的相对位置在排序前后不会发生改变。

冒泡排序的示例：

假设待排序序列为 5、1、4、2、8，如果采用冒泡排序对其进行升序排序，则整个排序过程如下所示：

第一轮排序能找到最大值，第二轮排序能找到第二大值，第三轮排序能找到第三大值。依次类推。

1. 第一轮排序：此时整个序列中的元素都位于待排序序列，依次比较每对相邻的元素，并对顺序不正确的元素进行位置交换。

   比较 4 次，从待排序序列中找到此次的最值 8，并将其放到了待排序序列的尾部，并入已排序序列中。

2. 第二轮排序：此时待排序序列只包含前 4 个元素，依次比较每对相邻元素，并对顺序不正确的元素进行位置交换。

   比较 3 次，从待排序序列中找到此次的最值 5，并将其放到了待排序序列的尾部，并入已排序序列中。
   

3. 第三轮排序：此时待排序序列包含前 3 个元素，依次比较每对相邻元素，并对顺序不正确的元素进行位置交换。

   比较 2 次，从待排序序列中找到此次的最值 4，并将其放到了待排序序列的尾部，并入已排序序列中。
   

4. 第四轮排序：此时待排序序列包含前 2 个元素，对其进行比较，并当顺序不正确时进行交换。

   比较 1 次，从待排序序列中找到此次的最值，并将其放到了待排序序列的尾部，并入已排序序列中。
   

5. 当进行第五轮冒泡排序时，由于待排序序列中仅剩 1 个元素，无论再进行相邻元素的比较，因此直接将其并入已排序序列中，此时的序列就认定为已排序好的序列。
   

冒泡排序的效率：

比较次数：

上面的例子一共有 5 个数字，第一次循环进行了 4 次比较，第二次循环进行了 3 次比较，第三次循环进行了 2 次比较，第四次循环进行了 1 次比较，比较次数为：4 + 3 + 2 + 1。

假设有 n 个数据项，推导公式为：(n - 1) + (n - 2) + (n - 3)+ ... +1 = n * (n - 1) / 2，因此冒泡排序真实的比较次数为 n * (n - 1) / 2。

n * (n - 1) / 2 = n² / 2 - n / 2 ，根据推导大 O 表示法的规则 2 只保留最高阶项，变为 n² / 2，根据规则 3 去除最高阶项的常量，变为 n²，因此冒泡排序的比较次数的大 O 表示法为 O(n²)。

交换次数：

因为不可能每次比较都交换一次，因此假设有两次比较才交换一次，因此冒泡排序真实的交换次数为 n * (n - 1) / 4。

由于常量不算在大 O 表示法中，因此可以认为冒泡排序的交换次数的大 O 表示法也为 O(n²)。

冒泡排序的代码实现：

需要两层循环来实现：

1. 外层循环是有几个元素就进行几次内层循环，寻找几遍最值。
2. 内层循环是两两比较相邻的元素，寻找每次的最值并将其排到最后。下一次进行内层循环的时候就不需要比较已被找到的最值了，因此内层循环内部遍历的次数会随着找到最值数量的增多越来越少。

// 冒泡排序：以升序为例
ArrayList.prototype.bubbleSort = function (item) {
  // 1. 获取列表长度
  var length = this.array.length

  // 2. 外层循环：第一次循环 i = length - 1，第一次循环 i = length - 2，直到 i = 0，每次内层循环都能找到一个最值并将其放置到末端，因此外层循环从大到小遍历，每次减少末端的已被放置的一个最值
  for (var i = length - 1; i >= 0 ; i--) {

    // 3. 内层循环，两两比较元素
    for (var j = 0; j < i; j++) {
        // 3.1. 比较两个相邻的元素，如果前一个元素大于后一个元素，那么交换两个元素的位置
        if (this.array[j] > this.array[j+1]) {
          var temp = this.array[j]
          this.array[j] = this.array[j+1]
          this.array[j+1] = temp
        }
      }
  }
}

// 测试冒泡排序：
list.bubbleSort()
console.log(list.toString()) // 1 2 4 5 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23