快捷導(dǎo)航

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

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

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

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

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

2）算法描述
       <1>比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
       <2>對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
       <3>針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
       <4>重復(fù)步驟1~3，直到排序完成。
3）javascript代碼實(shí)現(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]){ //相鄰元素進(jìn)行對(duì)比  
        var temp = arr[j+1];//交換元素  
        arr[j+1] = arr[j];  
        arr[j] = temp;  
      }  
    }  
  }  
  return arr;//返回?cái)?shù)組  
}  
  
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];//調(diào)用排序算法  
console.log(bubbleSort(arr));//控制臺(tái)輸出結(jié)果

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

function bubbleSort2(arr){  
  var i = arr.length -1;//開始時(shí)，掃描的最后位置  
  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)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。
改進(jìn)之后的算法如下：

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值，往后移動(dòng)一位  
  }  
  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)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: