冒泡排序是最慢的一种排序算法之一，但是也是一种最容易实现的排序算法。

之所以叫做冒泡排序，是因为这种排序算法排序时，数据值会像气泡一样从数组的一端跑到另一端。如果按照升序排列，那么较大的数值就会浮动到数组的右端，而较小的则浮动到数组的左端。

原理

以升序为例

  • 从开头进行相邻元素的两两比较
  • 如果第一个元素大于第二个元素，那么交换位置，否则继续往下比较
  • 直到最后，结束这一轮循环，最后一个值已经固定下来
  • 之后的循环只需要循环到固定下来的值之前即可
  • 当只剩下两个元素没有固定时，比较完成之后，结束整个循环

举例说明：要排序数组：[6,3,8,2,9,1]

第一趟排序：

　　　　第一次排序：6和3比较，6大于3，交换位置： 3 6 8 2 9 1

　　　　第二次排序：6和8比较，6小于8，不交换位置：3 6 8 2 9 1

　　　　第三次排序：8和2比较，8大于2，交换位置： 3 6 2 8 9 1

　　　　第四次排序：8和9比较，8小于9，不交换位置：3 6 2 8 9 1

　　　　第五次排序：9和1比较：9大于1，交换位置： 3 6 2 8 1 9

　　　　第一趟总共进行了5次比较， 排序结果： 3 6 2 8 1 9

第二趟排序：

　　　　第一次排序：3和6比较，3小于6，不交换位置：3 6 2 8 1 9

　　　　第二次排序：6和2比较，6大于2，交换位置： 3 2 6 8 1 9

　　　　第三次排序：6和8比较，6大于8，不交换位置：3 2 6 8 1 9

　　　　第四次排序：8和1比较，8大于1，交换位置： 3 2 6 1 8 9

　　　　第二趟总共进行了4次比较， 排序结果： 3 2 6 1 8 9

第三趟排序：

　　　　第一次排序：3和2比较，3大于2，交换位置： 2 3 6 1 8 9

　　　　第二次排序：3和6比较，3小于6，不交换位置：2 3 6 1 8 9

　　　　第三次排序：6和1比较，6大于1，交换位置： 2 3 1 6 8 9

　　　　第二趟总共进行了3次比较， 排序结果： 2 3 1 6 8 9

第四趟排序：

　　　　第一次排序：2和3比较，2小于3，不交换位置：2 3 1 6 8 9

　　　　第二次排序：3和1比较，3大于1，交换位置： 2 1 3 6 8 9

　　　　第二趟总共进行了2次比较， 排序结果： 2 1 3 6 8 9

第五趟排序：

　　　　第一次排序：2和1比较，2大于1，交换位置： 1 2 3 6 8 9

　　　　第二趟总共进行了1次比较， 排序结果： 1 2 3 6 8 9

最终结果：1 2 3 6 8 9

实现

  1. function bubbleSort(arr) {
  2.   let len = arr.length - 1,
  3.       outer, inner;
  5.   // 外层遍历 len-1 次，len 不断减少，里层比那里次数也不断减少
  6.   for (outer = len; outer > 0; outer--) {
  7.     // 里层遍历次数不断减少，初始只需要到 len-1 即可
  8.     for (inner = 0; inner < len; inner++) {
  9.       if (arr[inner] > arr[inner + 1]) {
  10.         [arr[inner], arr[inner + 1]] = [arr[inner + 1], arr[inner]];
  11.       }
  12.     }
  13.   }
  14. }

冒泡排序的时间复杂度是 冒泡排序 - 图1