【排序算法】-冒泡排序Bubble Sort
简介
冒泡排序，将临近的数字两两比较，按照大小顺序进行位置交换。
- 第一趟排序后，最大的数字（从小到大排序）或最小的数字（从大到小排序）被交换到最后一位，也就是说最后一位被确定；
- 第二趟确定倒数第二位数字；
- 以此类推，第三趟确定倒数第三位数字，第四趟确定倒数第4位数字，第五趟...
讲解
设示例数组为：[5,2,7,1,4,9,8]，小->大排序；
- 第一趟排序
-
第一次：[5,2,7,1,4,9,8]中5与2比较，5>2所以交换位置，数组变作为-->[2,5,7,1,4,9,8]；
-
第二次：[2,5,7,1,4,9,8]中5与7比较，5<7所以不交换位置，数组变作为-->[2,5,7,1,4,9,8]；
-
第三次：[2,5,7,1,4,9,8]中7与1比较，7>1所以交换位置，数组变作为-->[2,5,1,7,4,9,8]；
-
第四次：[2,5,1,7,4,9,8]中7与4比较，7>4所以交换位置，数组变作为-->[2,5,1,4,7,9,8]；
-
第五次：[2,5,1,4,7,9,8]中7与9比较，7<9所以不交换位置，数组变作为-->[2,5,1,4,7,9,8]；
-
第六次：[2,5,1,4,7,9,8]中9与8比较，9>8所以交换位置，数组变作为-->[2,5,1,4,7,8,9]；此时最大的数字9已经到了末尾。
-
第二趟排序
-
第一次：[2,5,1,4,7,8,9]中2与5比较，2<5所以不交换位置，数组变作为-->[2,5,1,4,7,8,9]；
-
第二次：[2,5,1,4,7,8,9]中5与1比较，5>1所以交换位置，数组变作为-->[2,1,5,4,7,8,9]；
-
第三次：[2,1,4,5,7,8,9]；
-
第四次：[2,1,4,5,7,8,9]；
-
第五次：[2,1,4,5,7,8,9]；这里不需要第六次比较，因为最后一个数已知是最大的，不需要再进行比较。同理第三趟不需要第五次比较，第四趟不需要第四次比较...
-
之后演示已无必要，哟哟切克闹，咳咳...
我们可以发现，该算法的复杂度为：(n-1)+(n-2)+...+2+1=n(n-1)/2
演示代码
//从小到大排序
function bubbleSort(array){
var tem = 0;
for (var i = 0; i < array.length; i++) {
for (var j = 0; j < array.length-i; j++) {
if(array[j]>array[j+1]){
tem = array[j];
array[j] = array[j+1];
array[j+1] = tem;
}
}
}
}
window.onload=function(){
var array = [2,3,1,4,9,7,5];
bubbleSort(array);
console.log(array);
}
代码执行结果
补充一：最近听见很多同学在说冒泡排序的复杂度为n的平方，百度一看似乎蛮多人也是这样认为的，看到的同学难免会有些为难究竟哪一个复杂度是正确的。
事实上，两者都是正确的，n(n-1)/2是比较精确，而n^2则是表示该算法复杂度的数量级。
n(n-1)/2 --->
(n^2-n)/2 --->
当n足够大时，-n的影响很小，而为了表示数量级n^2的系数1/2也去掉 --->
那么现在复杂度就是n^2了
