每日一算法之冒泡排序

ygyooo 發布于2019-08-20 16:25 / 3266人閱讀

摘要：冒泡排序算法是最慢的排序算法之一，但也是一種最容易實現的排序算法。雖然這個算法是正常運行了，但是執行過程，數據是如何變化的呢，讓我們一探究竟，這也能讓我們真正理解冒泡排序算法，而不是只記得代碼。

程序=數據結構+算法

在金庸武俠小說里，絕世高手的武功都是外功和內功的結合，你不僅需要能耍出亮瞎眼的招式，還得有能讓招式發揮出真正威力的內功；編程也是如此，我們在學習編程語言的語法、各種工具的使用的同時，應該要去好好學習數據結構和算法，了解一些底層的原理，這樣才能功力深厚。

好了，開始進入主題吧！

對計算機存儲的數據執行操作，排序是很常見的一種操作。一切按順序來，多方便。
這里我們先創建一個數組類。使用ES6的語法（class），趕潮流嘛。

js代碼如下：

class Arr {
      // 構造函數
      constructor(numElements) {
        // 存儲的數據
        this.data = []
        // 記錄數組下標
        this.index = 0
        // 生成數據的個數
        this.numElements = numElements
        // 初始化數組，數組長度為numElements,值為0-9
        for(let i = 0; i < numElements; i++) {
          this.data[i] = i
        }
      }
      // 重新設置數據，隨機生成
      setData() {
        for(let i = 0; i < this.numElements; i++) {
          // 生成隨機數據
          this.data[i] = Math.floor(Math.random() * (this.numElements + 1))
        }
      }
      // 將數據都置為0
      clear() {
        for(let i = 0; i < this.numElements; i++) {
          this.data[i] = 0
        }
      }
      // 插入數據
      insert(elements) {
        this.data[index++] = elements
      }
      // 將數據按格式讀取出來
      toString() {
        // 將數組轉為字符串
        let str = ""
        for(let i = 0; i < this.data.length; i++) {
          str += this.data[i] + " "
          if(i > 0 && i % 10 == 0) {
            str += "
"
          }
        }
        return str
      }
      // 將前后數據交換，用于之后的排序
      swap(arr, index1, index2) {
        let tmp = arr[index1]
        arr[index1] = arr[index2]
        arr[index2] = tmp
      }
    }

其中的setData()函數生成了存儲在數組中的隨機數字。Math.random()函數會生成[0,1)區間內的隨機數字，然后我們將其再乘以(numElements + 1)，這樣就能生成1-100的隨機數字集合了。這才是我們需要的數據。

測試一下：

const numElements = 100
const myNums = new Arr(numElements)
myNums.setData()
console.log(myNums.toString())

生成隨機數據并按格式打印：

好了，一個新的數組類已經創建完畢，接下來開始我們的冒泡排序了！

排序的核心思想是指對一組數據按照一定的順序重新排列。重新排列時用到的技術是一組嵌套的for循環。外循環負責遍歷數組的每一項，內循環負責比較元素。

冒泡排序算法是最慢的排序算法之一，但也是一種最容易實現的排序算法。

為什么叫冒泡排序呢，因為數據值就像氣泡一樣從數組的一端漂浮到另一端。假設正在將一組數字按照升序排序，較大的值會浮動到數組的右側，而較小值會浮動到數組的左側。因為該算法會多次在數組中移動，比較相鄰的數據，如果左側值大于右側值則會將它們互換。

先來一個簡單實例：

5 1 4 3 2

排序步驟：

1 4 3 2 5
1 3 2 4 5
1 2 3 4 5
至此，排序完成

接下來在剛剛創建的類中添加冒泡排序的代碼：

sort() {
  for(let outer = this.data.length; outer > 1; outer--) {
    for(let inner = 0; inner < outer - 1; inner++) {
      if(this.data[inner] > this.data[inner+1]) {
         this.swap(this.data, inner, inner+1)
      }
    }
  }
}

測試代碼：

const numElements = 10
const myNums = new Arr(numElements)
myNums.setData()
console.log(myNums.toString())
myNums.sort()
console.log(myNums.toString())

結果：

代碼非常簡短，就是嵌套for循環，然后比較前后大小。
雖然這個算法是正常運行了，但是執行過程，數據是如何變化的呢，讓我們一探究竟，這也能讓我們真正理解冒泡排序算法，而不是只記得代碼。

讓我們加一個toString()吧！

sort() {
        for(let outer = this.data.length; outer > 1; outer--) {
          for(let inner = 0; inner < outer - 1; inner++) {
            if(this.data[inner] > this.data[inner+1]) {
              this.swap(this.data, inner, inner+1)
            }
          }
          console.log(this.toString())
        }
      }

結果：

現在我們可以看到排序的具體過程了！

如何看代碼的意思呢，我們拿[9,8,7,6,5,4,3,2,1,0]這個數組來說：

首先我們這里完全需要進行9次遍歷，才能完全排好序。
我們先從數組的第一個值排起，需要比較9次
第一次 8，7，6，5，4，3，2，1，0，9 將9排到最后，現在不需要管9了，因為它是最大的，而且排到了最后，那么接下來就只需要比較8次了，再接著就是7，依次遞減，直到為1，最后結束循環
7 6 5 4 3 2 1 0 8 9
6 5 4 3 2 1 0 7 8 9
5 4 3 2 1 0 6 7 8 9
4 3 2 1 0 5 6 7 8 9
3 2 1 0 4 5 6 7 8 9
2 1 0 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
就是如此，這是最壞的情況，而算法就應該考慮最壞的情況來編寫，這樣才能適應各種情況。

好了，冒泡排序算法暫時分享到這，后續更新其他算法，求關注！

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

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

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

前端排序算法總結；前端面試題2.0；JavaScript異步編程

摘要：與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在，至少在被標準化的那一刻起，就支持異步編程了。然而異步編程真正發展壯大，的流行功不可沒。在握手過程中，端點交換認證和密鑰以建立或恢復安全會話。 1、前端排序算法總結排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較...

aaron 2019-08-01 17:38 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

摘要：與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在，至少在被標準化的那一刻起，就支持異步編程了。然而異步編程真正發展壯大，的流行功不可沒。在握手過程中，端點交換認證和密鑰以建立或恢復安全會話。 1、前端排序算法總結排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較...

ARGUS 2019-08-21 16:43 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

摘要：與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在，至少在被標準化的那一刻起，就支持異步編程了。然而異步編程真正發展壯大，的流行功不可沒。在握手過程中，端點交換認證和密鑰以建立或恢復安全會話。 1、前端排序算法總結排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較...

April 2019-08-30 15:53 評論0 收藏0
Java 數據結構與算法系列之冒泡排序

摘要：冒泡排序一種運行效率很低的排序算法，然而雖然排序效率低，確實排序入門很重的算法，因為冒泡排序的思路是最簡單最容易理解的排序算法了。二冒泡排序定義冒泡排序是一種通過兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止的交換排序。一、前言相信大部分同學都已經學過數據結構與算法這門課了，并且我們可能都會發現一個現象就是我們所學過的數據結構與算法類的書籍基本都是使用 C 語言來...

1treeS 2019-08-15 17:40 評論0 收藏0
PHP排序算法之冒泡排序

摘要：一冒泡排序原理對一組數據，比較相鄰數據的大小，將值小數據在前面，值大的數據放在后面。通過以上五輪排序，若干次比較，我們有理由推斷出一個結論對于一個長度為的數組，我們需要排序輪，每輪要比較次。一、冒泡排序　　原理：對一組數據，比較相鄰數據的大小，將值小數據在前面，值大的數據放在后面。（以下都是升序排列，即從小到大排列）　　舉例說明： $arr = array(6, 3, 8,...

Raaabbit 2019-07-01 10:30 評論0 收藏0