Bad programmers worry about the code. Good programmers worry about data structures and their relationships. —— Linus Torvalds
冒泡排序（Bubble Sort） 顾名思义，就是两两依次比较，如果顺序错误，就交换，直到没有交换，排序结束。有点类似水里的气泡一点一点浮上来，所以叫冒泡排序。
具体步骤如下（假设是从小到大排序）：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个（因为已经排序好了）。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
image
冒泡排序算法复杂度是：O(n2)，效率较低。
- 最坏时间复杂度 O(n2)
- 最优时间复杂度 O(n)
- 平均时间复杂度 O(n2)
- 最坏空间复杂度 总共 O(n)，需要辅助空间 O(1)
上代码：
// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log('Source array is [ %s ]\n', arr.join(', '))
// 冒泡排序
function bubbleSort(arr) {
const len = arr.length
let swapped // 是否有过交换，一旦没有任何元素交换，排序结束
let step = 1
for (let i = 0; i < len; i++) {
swapped = false
// 注意这里是len - i，每一轮都会把最大的元素放在最后，所以 len - i 后面的元素不用再比较
for (let j = 0; j < len - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素位置，这里是es6的方式
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
swapped = true
}
}
console.log('Step %d: [ %s ]', step++, arr.join(', '))
if (!swapped) break
}
console.log('\nSorted array is [ %s ]', arr.join(', '))
}
bubbleSort(arr)
结果：
Source array is [ 87, 94, 38, 54, 7, 89, 71, 82, 26, 20 ]
Step 1: [ 87, 38, 54, 7, 89, 71, 82, 26, 20, 94 ]
Step 2: [ 38, 54, 7, 87, 71, 82, 26, 20, 89, 94 ]
Step 3: [ 38, 7, 54, 71, 82, 26, 20, 87, 89, 94 ]
Step 4: [ 7, 38, 54, 71, 26, 20, 82, 87, 89, 94 ]
Step 5: [ 7, 38, 54, 26, 20, 71, 82, 87, 89, 94 ]
Step 6: [ 7, 38, 26, 20, 54, 71, 82, 87, 89, 94 ]
Step 7: [ 7, 26, 20, 38, 54, 71, 82, 87, 89, 94 ]
Step 8: [ 7, 20, 26, 38, 54, 71, 82, 87, 89, 94 ]
Step 9: [ 7, 20, 26, 38, 54, 71, 82, 87, 89, 94 ]
Sorted array is [ 7, 20, 26, 38, 54, 71, 82, 87, 89, 94 ]
注意：不要忘记对 swapped 和 j < len - i 的判断，否则会增添很多没有必要的比较，降低效率。
