#步骤拆解：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到未完成排序的最后一对，这样在数组的顶部自动生成一个不断加长的有序数列；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复1-3步，直到排序完成。
简单实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| function bubbleSort(arr){ var i = arr.length-1;//需要遍历的元素是从第一个到倒数第二个，因为每次比较的是arr[i]与arr[i+1] console.time('冒泡排序'); while(i>0){ var pos = 0;//每次遍历重新计算最后交换数据的位置 for(var j=0;j<i;j++){ if(arr[j]>arr[j+1]){ pos =j; arr[j]^=arr[j+1];//亦或可以交换两个不同值的变量的值，如果值相同交换后变成0，需要格外小心。 arr[j+1]^=arr[j]; arr[j]^=arr[j+1]; } } i=pos;//每次遍历后将下次遍历的终点设置为数组顶部有序数列的开始位置（有序数列不参与下次遍历和交换） } console.timeEnd('冒泡排序'); return arr; }
|
#小结：
冒泡排序时间复杂度为O(n)-O(n^2),空间复杂度为O(1),稳定
图解：
