JavaScript實現冒泡排序

Aomine 發布于2019-08-22 16:01 / 1304人閱讀

說明

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

實現原理

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

好的，我們先來實現找數組中的最大數，并把他放到數組最后。

var arr = [3,4,1,2];
// 遍歷數組，次數就是arr.length - 1
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)  // [3, 1, 2, 4]

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

var arr = [3,4,1,2];
// 遍歷數組，次數就是arr.length - 1
for (var j = 0; j < arr.length - 1; j++) {
    // 這里 i < arr.length - 1 ，要思考思考合適嗎？我們下面繼續說
    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]

雖然上面的代碼已經實現冒泡排序了，但就像注釋中提到的，內層 for 循環的次數寫成，i < arr.length - 1 ，是不是合適呢？
我們想一下，當第一次，找到最大數，放到最后，那么下一次，遍歷的時候，是不是就不能把最后一個數算上了呢？因為他就是最大的了，不會出現，前一個數比后一個數大，要交換位置的情況，所以內層 for 循環的次數，改成 i < arr.length - 1 -j ，才合適，看下面的代碼。

var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  for (var j = 0; j < arr.length - 1; j++) {
    // 這里要根據外層for循環的 j，逐漸減少內層 for循環的次數
    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);

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

完整代碼

var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  var max = arr.length - 1;
  for (var j = 0; j < max; j++) {
    // 聲明一個變量，作為標志位
    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);

性能

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

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

總結

1、外層 for 循環控制循環次數
2、內層 for 循環進行兩數交換，找每次的最大數，排到最后
3、設置一個標志位，減少不必要的循環

好的，下一篇文章，來實現下冒泡排序的可視化，把冒泡排序的過程展示出來。
JavaScript實現冒泡排序可視化

云服務器 GPU云服務器冒泡排序前端冒泡排序冒泡排序代碼 js冒泡排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/93970.html

JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
JavaScript實現冒泡排序可視化

摘要：說明上次寫了實現冒泡排序，只是簡單的說了冒泡排序算法是什么，怎么實現，這次來實現將冒泡排序的過程展現出來。總結上面的兩個版本的思路基本一樣，用一句話概括就是，記錄冒泡排序所有的改變，將這些改變一步一步的顯示出來。說明上次寫了 JavaScript實現冒泡排序，只是簡單的說了冒泡排序算法是什么，怎么實現，這次來實現將冒泡排序的過程展現出來。解釋先來個簡單的版本，看效果圖 sh...

RebeccaZhong 2019-08-22 16:01 評論0 收藏0
Javascript實現冒泡排序與快速排序以及對快速排序的性能優化

摘要：實現快速排序介紹通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。冒泡排序介紹重復遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后冒泡到數組的末端。假如數組...

dadong 2019-08-23 15:08 評論0 收藏0
javascript冒泡排序

摘要：冒泡排序可謂是最經典的排序算法了，它是基于比較的排序算法，其優點是實現簡單，排序數量較小時性能較好。也可以實現大數放在前面，小數放在后面，如果前面的數據比后面的小，就交換兩個的位置。要實現上述規則需要用到兩層循環。冒泡排序可謂是最經典的排序算法了，它是基于比較的排序算法，其優點是實現簡單，排序數量較小時性能較好。算法原理相鄰的數據進行兩兩比較，小數放在前面，大數放在后面，如果前面...

wanghui 2019-08-26 12:10 評論0 收藏0
JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0