JavaScript實現(xiàn)經(jīng)典排序算法之冒泡排序
冒泡排序可謂是最經(jīng)典的排序算法了，它是基于比較的排序算法，時間復雜度為O(n^2)，其優(yōu)點是實現(xiàn)簡單，n較小時性能較好。
1）算法原理
相鄰的數(shù)據(jù)進行兩兩比較，小數(shù)放在前面，大數(shù)放在后面，這樣一趟下來，最小的數(shù)就被排在了第一位，第二趟也是如此，如此類推，直到所有的數(shù)據(jù)排序完成。
2）算法描述
<1>比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
<2>對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數(shù)；
<3>針對所有的元素重復以上的步驟，除了最后一個；
<4>重復步驟1~3，直到排序完成。
3）javascript代碼實現(xiàn)
function bubbleSort(arr){
var len = arr.length;
for (var i = 0; i < len; i++) {
for(var j = 0; j < len - i -1; j++){
if(arr[j]>arr[j+1]){ //相鄰元素進行對比
var temp = arr[j+1];//交換元素
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;//返回數(shù)組
}
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];//調用排序算法
console.log(bubbleSort(arr));//控制臺輸出結果
這個算法是最基本的實現(xiàn)方法，接著進行改進這個算法，通過設置一個標志性的變量position，用于記錄每趟排序中最后一次進行交換的位置。因為position位置之后的記錄都已經(jīng)排序好了，所以進行下一趟排序時只需要掃描到position的位置就好。
改進之后的算法如下：
function bubbleSort2(arr){
var i = arr.length -1;//開始時，掃描的最后位置
while(i>0){
var position = 0;//標志性變量，表示當前排序中交換的位置
for(var j = 0; j < i; j ++){
if(arr[j]>arr[j+1]){
position = j;
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
i = position;
}
return arr;
}
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];
console.log(bubbleSort2(arr));
傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。
改進之后的算法如下：
function bubbleSort3(arr){
var low = 0;
var high = arr.length-1;
var temp;
while(low < high){//找到最大值
for(var j = low ; j < high ; j++){
if (arr[j]> arr[j+1]) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
--high;//修改high值，向前移一位
}
while(low > high){//找到最小值
for(var j = high ;j > low; j--){
if (arr[j]> arr[j+1]) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
++low;//修改low值，往后移動一位
}
return arr;
}
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];
console.log(bubbleSort3(arr));
4）算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(n2)
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
動態(tài)更新highcharts數(shù)據(jù)的實現(xiàn)方法
下面小編就為大家?guī)硪黄獎討B(tài)更新highcharts數(shù)據(jù)的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-05-05
這篇文章主要介紹了如何實現(xiàn)iframe父子傳參通信，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-02-02
根據(jù)IP的地址，區(qū)分不同的地區(qū)，查看不同的網(wǎng)站頁面的js代碼
在朋友的幫助下，找到一個比較方便的方法，就是把以下代碼，加入我們自己需要跳轉的頁面里，這樣做還是不錯的呢2013-02-02
這篇文章介紹了JS定時刷新頁面及跳轉頁面的方法，有需要的朋友可以參考一下2013-07-07
大家都知道Promise解決了回調地獄的問題,“回調地獄”所說的嵌套其實是指異步的嵌套,它帶來了兩個問題:可讀性的問題和信任問題,下面這篇文章主要給大家介紹了關于JS中promise特點與信任問題解決的相關資料,需要的朋友可以參考下2022-06-06
初次見到這樣語句 a=a || [] 還有些納悶，因為在其他語言中沒見過有如此用法。2010-05-05
vue基于ElementUI動態(tài)設置表格高度的3種方法
ElementUI+vue動態(tài)設置表格高度的幾種方法,拋磚引玉,還有其它方法動態(tài)設置表格高度,大家可以開動腦筋2025-02-02
2009-07-07
這篇文章主要為大家詳細介紹了JS實現(xiàn)縱向輪播圖的初級版，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
本文是對Js中單引號與雙引號的使用進行了總結介紹，需要的朋友可以過來參考下，希望對大家有所幫助2013-11-11