JS排序之冒泡排序詳解

發(fā)布時(shí)間：2020-09-13 08:38:04 來源：腳本之家閱讀：156 作者：Blue-Beginner 欄目：web開發(fā)

本文為大家分享了JS冒泡排序的具體代碼，供大家參考，具體內(nèi)容如下

說明

時(shí)間復(fù)雜度指的是一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間
空間復(fù)雜度指運(yùn)行完一個(gè)程序所需內(nèi)存的大小
穩(wěn)定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不穩(wěn)定指，如果a=b，a在b的前面，排序后可能會(huì)交換位置

--JS冒泡排序--

原理

依次比較相鄰的兩個(gè)值，如果后面的比前面的小，則將小的元素排到前面。依照這個(gè)規(guī)則進(jìn)行多次并且遞減的迭代，直到順序正確。

時(shí)間復(fù)雜度，空間復(fù)雜度，穩(wěn)定性

平均時(shí)間復(fù)雜度O(n*n)
最好情況O(n)
最差情況O(n*n)
空間復(fù)雜度O(1)
穩(wěn)定性：穩(wěn)定

冒泡排序的寫法

var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
  for(i=0;i<arr.length-1;i++){
    for(j=0;j<arr.length-1-i;j++){
      if(arr[j]>arr[j+1]){
        var temp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
      }
    }
  }
  return arr;
}
sortarr(examplearr);
console.log(examplearr);

解析

兩個(gè)循環(huán)

當(dāng)i=0的時(shí)候，里面的循環(huán)完整執(zhí)行，從j=0執(zhí)行到j(luò)=6,這也就是第一遍排序，結(jié)果是將最大的數(shù)排到了最后，這一遍循環(huán)結(jié)束后的結(jié)果應(yīng)該是[8,15,88,55,76,21,39,94]

當(dāng)i=1的時(shí)候，里面的循環(huán)再次完整執(zhí)行，由于最大的數(shù)已經(jīng)在最后了，沒有必要去比較數(shù)組的最后兩項(xiàng)，這也是j<arr.length-1-i的巧妙之處，結(jié)果是[8,15,55,76,21,39,88,94]

說到這里，規(guī)律就清楚了，每次將剩下數(shù)組里面最大的一個(gè)數(shù)排到最后面，當(dāng)?shù)谝粋€(gè)循環(huán)執(zhí)行到最后的時(shí)候，也就是i=6,此時(shí)，j=0,只需要比較數(shù)組的第一和第二項(xiàng)，比較完畢，返回。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。

向AI問一下細(xì)節(jié)

JS排序之冒泡排序詳解

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽