JavaScript實(shí)現(xiàn)冒泡排序

Aomine 發(fā)布于2019-08-22 16:01 / 1300人閱讀

說明

對數(shù)組進(jìn)行冒泡排序算是比較簡單的，冒泡排序也是容易理解的一種排序算法了，在面試的時候，很可能就會問到。

實(shí)現(xiàn)原理

數(shù)組中有 n 個數(shù)，比較每相鄰兩個數(shù)，如果前者大于后者，就把兩個數(shù)交換位置；這樣一來，第一輪就可以選出一個最大的數(shù)放在最后面；那么經(jīng)過 n-1（數(shù)組的 length - 1） 輪，就完成了所有數(shù)的排序。

好的，我們先來實(shí)現(xiàn)找數(shù)組中的最大數(shù)，并把他放到數(shù)組最后。

var arr = [3,4,1,2];
// 遍歷數(shù)組，次數(shù)就是arr.length - 1
for (var i = 0; i < arr.length - 1; i++) {
    // 如果前一個數(shù) 大于 后一個數(shù) 就交換兩數(shù)位置
    if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
    }
}
console.log(arr)  // [3, 1, 2, 4]

我們能找到數(shù)組中最大的數(shù)，放到最后，這樣重復(fù) arr.length - 1 次，便可以實(shí)現(xiàn)數(shù)組按從小到大的順序排好了。

var arr = [3,4,1,2];
// 遍歷數(shù)組，次數(shù)就是arr.length - 1
for (var j = 0; j < arr.length - 1; j++) {
    // 這里 i < arr.length - 1 ，要思考思考合適嗎？我們下面繼續(xù)說
    for (var i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            var temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
}
console.log(arr)  // [1,2,3,4]

雖然上面的代碼已經(jīng)實(shí)現(xiàn)冒泡排序了，但就像注釋中提到的，內(nèi)層 for 循環(huán)的次數(shù)寫成，i < arr.length - 1 ，是不是合適呢？
我們想一下，當(dāng)?shù)谝淮危业阶畲髷?shù)，放到最后，那么下一次，遍歷的時候，是不是就不能把最后一個數(shù)算上了呢？因?yàn)樗褪亲畲蟮牧耍粫霈F(xiàn)，前一個數(shù)比后一個數(shù)大，要交換位置的情況，所以內(nèi)層 for 循環(huán)的次數(shù)，改成 i < arr.length - 1 -j ，才合適，看下面的代碼。

var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  for (var j = 0; j < arr.length - 1; j++) {
    // 這里要根據(jù)外層for循環(huán)的 j，逐漸減少內(nèi)層 for循環(huán)的次數(shù)
    for (var i = 0; i < arr.length - 1 - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
  return arr;
}
bubbleSort(arr);

我們想下這個情況，當(dāng)原數(shù)組是，
arr = [1,2,4,3];
在經(jīng)過第一輪冒泡排序之后，數(shù)組就變成了
arr = [1,2,3,4];
此時，數(shù)組已經(jīng)排序完成了，但是按上面的代碼來看，數(shù)組還會繼續(xù)排序，所以我們加一個標(biāo)志位，如果某次循環(huán)完后，沒有任何兩數(shù)進(jìn)行交換，就將標(biāo)志位設(shè)置為 true，表示排序完成，這樣我們就可以減少不必要的排序，提高性能。

完整代碼

var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  var max = arr.length - 1;
  for (var j = 0; j < max; j++) {
    // 聲明一個變量，作為標(biāo)志位
    var done = true;
    for (var i = 0; i < max - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
      }
    }
    if (done) {
      break;
    }
  }
  return arr;
}
bubbleSort(arr);

性能

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

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

總結(jié)

1、外層 for 循環(huán)控制循環(huán)次數(shù)
2、內(nèi)層 for 循環(huán)進(jìn)行兩數(shù)交換，找每次的最大數(shù)，排到最后
3、設(shè)置一個標(biāo)志位，減少不必要的循環(huán)

好的，下一篇文章，來實(shí)現(xiàn)下冒泡排序的可視化，把冒泡排序的過程展示出來。
JavaScript實(shí)現(xiàn)冒泡排序可視化