冒泡排序:就是將一個數組中的元素按照從大到小或者從小到大的順序進行排列。
var array=[9,8,7,6,5,4,3,2,1];
第一輪比較:8,7,6,5,4,3,2,1,9 交換了8次 i=0 j=array.length-1-i
第二輪比較:7,6,5,4,3,2,1,8,9 交換了7次 i=1 j=array.length-1-i
第三輪比較:6,5,4,3,2,1,7,8,9 交換了6次 i=2 j=array.length-1-i
第四輪比較:5,4,3,2,1,6,7,8,9 交換了5次 i=3 j=array.length-1-i
第五輪比較:4,3,2,1,5,6,7,8,9 交換了4次 i=4 j=array.length-1-i
第六輪比較:3,2,1,4,5,6,7,8,9 交換了3次 i=5 j=array.length-1-i
第七輪比較:2,1,3,4,5,6,7,8,9 交換了2次 i=6 j=array.length-1-i
第八輪比較:1,2,3,4,5,6,7,8,9 交換了1次 i=7 j=array.length-1-i
代碼實現:
var temp; var array=[9,8,7,6,5,4,3,2,1]; //外循環控制輪數 for(var i=0;i<array.length-1;i++){ //內循環控制比較次數 for(var j=0;j<array.length-1-i;j++){ if(array[j]>array[j+1]){ //交換兩個變量 temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } console.log(array);
代碼優化:
var temp,bool,m=0; var array=[9,8,7,6,5,4,3,2,1]; for(var i=0;i<array.length-1;i++){ //開閉原則中的開關 bool = true; for(var j=0;j<array.length-1-i;j++){ if(array[j]>array[j+1]){ //交換兩個變量 temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; bool=false;//將開關關閉 } } //如果內循環中的if沒有被執行(開關關閉,執行下面的語句); if(bool){ break; } m++; } console.log(array+",比較"+m+"輪");
備注:比較輪數最好情況為0輪,最壞為8輪
我們再來看個冒泡排序的算法
//javascript冒泡排序,直接添加到基礎類型的原型上 //這裡用一個javascript語言精粹上的 代碼,為基礎類型原型添加方法, // 因為Array,String他們自身也是構造函數,他們創建對象也是通過new 構造函數行的,因此Array.prototype,String.prototype都指向了Function.prototype // Array.method的時候,先訪問Array自身函數對象沒有method方法,接著Array.prototype仍沒有,接著Function.prototype找到了 Function.prototype.method = function (name, func) { if(!this.prototype[name]){ //最好先判斷一下是原型中否有這個方法,如果沒有再添加 this.prototype[name] = func; } return this; }; Array.method('bubble',function(){ // 冒泡算法 總共循環數組的長度次,即len次,每次將最小的放最後 var len = this.length; var i = 0, j = 0, tmp =0; for (i=0 ; i < len; i++) { for ( j = 0; (j +1) < len-i; j++) { console.log() if ( this[j] > this[j+1] ){ tmp = this[j]; this[j] = this[j+1]; this[j+1] = tmp; } }; }; return this; }); alert([21,32,1,31,22,45,68,37,].bubble());
看了另一個前端工程師,西風瘦馬的代碼,在第一層for循環加入初始化一個exchange交換標志為false,當有交換發生時,則變為true,在第二層for循環結束後加入一個判斷,如果為false,即從前往後對比沒有交換,證明已經大小順序正確,即可break來跳出外層for循環。
//需要排序的數組 var list = Array(23, 45, 18, 37, 92, 13, 24); //數組長度 var n = list.length; //交換順序的臨時變量 var tmp;// //交換標志 var exchange; //最多做n-1趟排序 for (var time = 0; time <n - 1; time ++) { exchange = false; for (var i = n - 1; i> time; i–-) { if (list[i] <list[i - 1]) { exchange = true; tmp = list[i - 1]; list[i - 1] = list[i]; list[i] = tmp; } } //若本趟排序未發生交換,提前終止算法 if (!exchange) { break; } } alert(‘數組排序後為:' + list + ‘,n共排了' + time + ‘趟');
之前還收藏過一個網友的算法,也相當不錯,大家看下
function BubbleSort(array) { var length = array.length; var temp; var isSort=false; for(var i = 1; i < length; i++) { isSort = false; for(var j = 0; j < length - i; j++) { if(array[j] > array[j+1]) { //交換 temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; isSort = true; } } if(!isSort) break; //如果沒有發生交換,則退出循環 } } var array =[10,-3,5,34,-34,5,0,9]; BubbleSort(array); for(var i=0;i< array.length;i++) { document.write(array[i]+ " "); }
好了,今天就先給大家總結這些吧,希望對小伙伴們學習JavaScript冒泡排序能夠有所幫助