冒泡排序

概念

冒泡排序核心概念在于每次都会对相邻的两个数进行比较

在升序排序的情况下，交换的条件需要满足，左边的数据大于右边的数据
在降序排序的情况下，交换的条件需要满足，左边的数据小于右边的数据

冒泡排序的思想是每一次遍历未排序的数列后，都会将一个数据元素浮上去（这个数据会排序到左侧或者右侧，具体取决于升序还是降序）。

冒泡排序的需要 N - 1 轮排序，其中 N 为数组的长度

例如有一个如下的数组，长度为 5，那么总共需要 4 轮排序，每一轮排序都是左右两个数相互比较并判断是否需要交换位置。

const data = [5, 1, 2, 9, -1];

进行冒泡（升序）排序：

第一轮
- 5 与 1 进行比较，5 > 1，则两个数交换位置。
  js
```
[1, 5, 2, 9, -1];
```
- 5 与 2 进行比较， 5 > 2，则两个数交换位置。
  js
```
[1, 2, 5, 9, -1];
```
- 5 与 9 进行比较， 5 < 9，则不做处理。
- 9 与 -1 进行比较， 9 > -1，则两个数交换位置。
  js
```
[1, 2, 5, -1, 9];
```
第二轮
- 1 与 2 进行比较，1 < 2，则不做处理。
- 2 与 5 进行比较，2 < 5，则不做处理。
- 5 与 -1 进行比较，5 > -1，则两个数交换位置。
  js
```
[1, 2, -1, 5, 9];
```
- 5 与 9 进行比较，5 > 9，则不做处理。
第三轮
- 1 与 2 进行比较，1 < 2，则不做处理。
- 2 与 -1 进行比较，2 > -1，则两个数交换位置。
  js
```
[1, -1, 2, 5, 9];
```
- 2 与 5 进行比较，2 < 5，则不做处理。
- 5 与 9 进行比较，5 > 9，则不做处理。
第四轮
- 1 与 -1 进行比较，1 > -1，则两个数交换位置。
  js
```
[-1, 1, 2, 5, 9];
```
- 1 与 2 进行比较，1 < 2，则不做处理。
- 2 与 5 进行比较，2 < 5，则不做处理。
- 5 与 9 进行比较，5 > 9，则不做处理。

最终执行了四轮排序操作，至此整个冒泡排序结束。

排序后的最终结果：[-1, 1，2, 5, 9]。

算法实现（JavaScript）

可以看出，每次进行新一轮排序，都是两个相邻的数彼此判断是否需要交换位置，那么需要用到两个 for 循环。

外层的 for 循环负责遍历新一轮排序，内层的 for 循环负责交换新一轮排序下的元素。

代码实现如下：

function bubbleSort(data) {
   const len = data.length;
   // 前面提到过，冒泡排序最终需要进行 N - 1 轮排序，其中 N 为数组的长度
   const sortCount = len - 1;
   for (let i = 0; i < sortCount; i++) {
      for (let j = 0; j < len; j++) {
         if (data[j] > data[j + 1]) {
            const temp = data[j];
            data[j] = data[j + 1];
            data[j + 1] = temp;
         }
      }
   }
   return data;
}

执行该函数得到以下的输出结果：

bubbleSort([5, 1, 2, 9, -1]); // [-1, 1，2, 5, 9]

着手优化

这种为了交换数据，开辟一个临时变量的做法不能说不好，但是还能更简洁（装逼）的做法：

原方案：

function bubbleSort(data) {
   //...
   const temp = data[j];
   data[j] = data[j + 1];
   data[j + 1] = temp;
   ///...
}

改进后：

function bubbleSort(data) {
   // ...
   [data[j + 1], data[j]] = [data[j], data[j + 1]];
   // ...
}

我们还可以借助位运算，达到更快的值交换：

data[j] ^= data[j + 1];
data[j + 1] ^= data[j];
data[j] ^= data[j + 1];

更进一步优化

通过上面的排序步骤示例，我们不难看每一轮比较完毕后，排序好的数据不再参与任何的位置交换。

每一轮比较，参与比较的数据的个数 = 总轮数 - 当前的轮数，也就是说我们不必每一轮都需要将数组中的每个元素进行比较，这是毫无意义的。

而且当数据量过大时，排序耗时会很长。

下面是优化后的排序算法：

function bubbleSort(data) {
   const len = data.length;
   const sortCount = len - 1;
   for (let i = 0; i < sortCount; i++) {
      // 内循环每次需要比较的个数为总个数减去当前的趟数
      for (let j = 0; j < len - i; j++) {
         if (data[j] > data[j + 1]) {
            [data[j + 1], data[j]] = [data[j], data[j + 1]];
         }
      }
   }
   return data;
}

算法复杂度

时间复杂度: O(n²)

空间复杂度: O(1)

总结

冒泡排序是一种最基础、也是性能最低的排序算法，因为它的时间复杂度取决于数组的长度，数组越大，其排序的性能也就越低。

一般不会用到这个算法，但是了解它的核心概念是非常重要的。

冒泡排序 ​

概念 ​

进行冒泡（升序）排序： ​

算法实现（JavaScript） ​

着手优化 ​

更进一步优化 ​

算法复杂度 ​

总结 ​