成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

每日一算法之冒泡排序

ygyooo / 3272人閱讀

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

程序=數(shù)據(jù)結(jié)構(gòu)+算法

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

好了，開始進(jìn)入主題吧！

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

js代碼如下：

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

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

測試一下：

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

生成隨機(jī)數(shù)據(jù)并按格式打?。?/p>

好了，一個新的數(shù)組類已經(jīng)創(chuàng)建完畢，接下來開始我們的冒泡排序了！

排序的核心思想是指對一組數(shù)據(jù)按照一定的順序重新排列。重新排列時用到的技術(shù)是一組嵌套的for循環(huán)。外循環(huán)負(fù)責(zé)遍歷數(shù)組的每一項，內(nèi)循環(huán)負(fù)責(zé)比較元素。

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

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

先來一個簡單實例：

5 1 4 3 2

排序步驟：

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

接下來在剛剛創(chuàng)建的類中添加冒泡排序的代碼：

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())

結(jié)果：

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

讓我們加一個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())
        }
      }

結(jié)果：

現(xiàn)在我們可以看到排序的具體過程了！

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

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

好了，冒泡排序算法暫時分享到這，后續(xù)更新其他算法，求關(guān)注！

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/82918.html

相關(guān)文章

  • 前端排序算法總結(jié)；前端面試題2.0；JavaScript異步編程

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

    aaron 評論0 收藏0

  • 前端排序算法總結(jié)；前端面試題2.0；JavaScript異步編程

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

    ARGUS 評論0 收藏0

  • 前端排序算法總結(jié)；前端面試題2.0；JavaScript異步編程

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

    April 評論0 收藏0

  • Java 數(shù)據(jù)結(jié)構(gòu)與算法系列之冒泡排序

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

    1treeS 評論0 收藏0

  • PHP排序算法之冒泡排序

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

    Raaabbit 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<