冒泡排序是一种较简单排序算法。它重复地走访过要排序的元素列，依次比较和交换两个相邻的元素，每一次遍历会将一个元素“浮”到数列的顶端，所以命名为冒泡排序。
排序过程对于数组[5, 10, 13, 15, 10, 100, 78, 46]，要求从小到大排序。
从下标为j开始，比较相邻两个元素，如果arr[j] > arr[j + 1]，则交换元素。然后j++，比较下一对元素。重复上一步操作，直到这一次遍历结束。从数组开始，重复1、2操作。结束的时候，数组变成有序的数组。js代码如下
var array = [5, 10, 13, 15, 10, 100, 78, 46];function bubbing(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - 1; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } console.log(arr);}bubbing(array); 时间复杂度长度为n的数组，假设冒泡排序时遇到最坏的情况，数组是反序的。每一趟需要交换 n - i 次。那么总共需要交换次数C为：
C = n - 1 + n - 2 + …… + 1
根据ssdkl求和公式可得：
C = n * (n - 1) / 2
那么冒泡排序的时间复杂度为：O(n²)
但是经过优化的冒泡排序可以在最好的情况，时间复杂度为O(n)，下面第二次优化会讲。
优化第一次优化
由于每次都会把一个最大或最小的元素排列到该去的位置，所以下一次遍历的时候就可以不遍历已有序的部分。
function bubbing_2(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } console.log(arr);}bubbing_2(array);第二次优化
第一次优化减少了要遍历的次数，第二次优化则是加了一个岗哨。每一次遍历的时候判断是否发生过元素交换操作，如果没有没有发生，那就说明数组已经有序，则终止排序。
当数组本身就是有序的时候，只是遍历了一次，没有经过交换就完成排序。时间负责度为O(n)。
function bubbing_2(arr) { for (let i = 0; i < arr.length; i++) { let count = 0; for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; count++; } } if (count == 0) break; } console.log(arr);}bubbing_2(array);第三次优化
第三次优化的思路是从数组的两头分别进行冒泡操作，假如要从小到大排序。那正向就是将最小的元素放到末尾，反向就是将最大的元素放到头部。这种方案又称为鸡尾酒排序、来回排序
鸡尾酒排序的方式并不会减少交换元素的次数，这点非常重要。它对性能的优化在于某些情况下，遍历的次数会减少。
例如：数组[2, 3, 4, 1] ，需要经过4次外层遍历才能有序。而用鸡尾酒排序的思路，外层只需要一次即可。
function bubbing_3(arr) { const len = arr.length; const loop = Math.floor((len + 1) / 2); // 既然每次都将两个元素排列到对的地方， // 那外层的遍历次数就可以减少为原来的一半 for (let i = 0; i < loop; i++) { let count = 0; for (let j = i + 1; j < len - 1; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; count++; } } for (let k = len - i - 1; k > 0; k--) { if (arr[k] < arr[k - 1]) { const temp = arr[k]; arr[k] = arr[k - 1]; arr[k - 1] = temp; count++; } } if (count == 0) break; } console.log(arr);}bubbing_3(array); 思考冒泡排序是最基础的排序方式了，和交换排序、插入排序一样，思路简单，容易掌握。所以我一开始把冒泡排序写成交换排序，尴尬！
思考的问题有两点：
在鸡尾酒排序的方案中，仔细思考到底是哪里提升性能的时候，走了一个误区。以为交换次数会变少，其实不是。鸡尾酒排序方案开始外层写的是循环到n结束，后来想到是从两头开始排序的，一次两个，岂不是可以减少外层次数，然后想了一下果然可以。（其实前面三段代码中外层的n都可以写成n - 1）