快捷導(dǎo)航

JavaScript實現(xiàn)經(jīng)典排序算法之冒泡排序

更新時間：2016年12月28日 08:37:31 作者：Wendy-lxq

這篇文章主要介紹了JavaScript實現(xiàn)經(jīng)典排序算法之冒泡排序，具有一定的參考價值，感興趣的小伙伴們可以參考一下

冒泡排序可謂是最經(jīng)典的排序算法了，它是基于比較的排序算法，時間復(fù)雜度為O(n^2)，其優(yōu)點是實現(xiàn)簡單，n較小時性能較好。

1）算法原理
相鄰的數(shù)據(jù)進行兩兩比較，小數(shù)放在前面，大數(shù)放在后面，這樣一趟下來，最小的數(shù)就被排在了第一位，第二趟也是如此，如此類推，直到所有的數(shù)據(jù)排序完成。

2）算法描述
       <1>比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
       <2>對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；
       <3>針對所有的元素重復(fù)以上的步驟，除了最后一個；
       <4>重復(fù)步驟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];//調(diào)用排序算法  
console.log(bubbleSort(arr));//控制臺輸出結(jié)果

這個算法是最基本的實現(xiàn)方法，接著進行改進這個算法，通過設(shè)置一個標(biāo)志性的變量position，用于記錄每趟排序中最后一次進行交換的位置。因為position位置之后的記錄都已經(jīng)排序好了，所以進行下一趟排序時只需要掃描到position的位置就好。
改進之后的算法如下：

function bubbleSort2(arr){  
  var i = arr.length -1;//開始時，掃描的最后位置  
  while(i>0){  
    var position = 0;//標(biāo)志性變量，表示當(dāng)前排序中交換的位置  
    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)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: