每日一算法之冒泡排序

ygyooo 發(fā)布于2019-08-20 16:25 / 3313人閱讀

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

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

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

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

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

js代碼如下：

class Arr {
      // 構(gòu)造函數(shù)
      constructor(numElements) {
        // 存儲(chǔ)的數(shù)據(jù)
        this.data = []
        // 記錄數(shù)組下標(biāo)
        this.index = 0
        // 生成數(shù)據(jù)的個(gè)數(shù)
        this.numElements = numElements
        // 初始化數(shù)組，數(shù)組長(zhǎng)度為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ù)按格式讀取出來(lái)
      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ù)生成了存儲(chǔ)在數(shù)組中的隨機(jī)數(shù)字。Math.random()函數(shù)會(huì)生成[0,1)區(qū)間內(nèi)的隨機(jī)數(shù)字，然后我們將其再乘以(numElements + 1)，這樣就能生成1-100的隨機(jī)數(shù)字集合了。這才是我們需要的數(shù)據(jù)。

測(cè)試一下：

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

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

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

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

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

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

先來(lái)一個(gè)簡(jiǎn)單實(shí)例：

5 1 4 3 2

排序步驟：

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

接下來(lái)在剛剛創(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)
      }
    }
  }
}

測(cè)試代碼：

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

結(jié)果：

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

讓我們加一個(gè)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)在我們可以看到排序的具體過(guò)程了！

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

首先我們這里完全需要進(jìn)行9次遍歷，才能完全排好序。
我們先從數(shù)組的第一個(gè)值排起，需要比較9次
第一次 8，7，6，5，4，3，2，1，0，9 將9排到最后，現(xiàn)在不需要管9了，因?yàn)樗亲畲蟮?，而且排到了最后，那么接下?lái)就只需要比較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)該考慮最壞的情況來(lái)編寫，這樣才能適應(yīng)各種情況。

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

云服務(wù)器 GPU云服務(wù)器冒泡排序前端冒泡排序冒泡排序代碼 js冒泡排序

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/82918.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

ygyooo

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow升級(jí)

閱讀 3821·2023-04-25 18:41
程序員若不想吃青春飯，就得不斷進(jìn)階提升

閱讀 1286·2021-11-11 16:55
服務(wù)器主機(jī)用什么cpu使用率-開(kāi)我的世界服務(wù)器需要什么CPU，怎么樣？

閱讀 1911·2021-09-22 15:54
手機(jī)怎么遠(yuǎn)程云主機(jī)名-云主機(jī)怎么遠(yuǎn)程操作？

閱讀 3145·2021-09-22 15:51
Web技術(shù)的前世今生（一）

閱讀 3608·2019-08-30 15:55
CSS基礎(chǔ)-如何用border寫三角形？

閱讀 2006·2019-08-30 14:19
切圖崽的自我修養(yǎng)－優(yōu)化圖片加載流程

閱讀 1396·2019-08-29 10:57
html5之canvas

閱讀 1773·2019-08-29 10:56

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

每日一算法之冒泡排序

相關(guān)文章

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

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

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

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

PHP排序算法之冒泡排序

發(fā)表評(píng)論

0條評(píng)論

ygyooo

男|高級(jí)講師

TA的文章

tensorflow升級(jí)

程序員若不想吃青春飯，就得不斷進(jìn)階提升

服務(wù)器主機(jī)用什么cpu使用率-開(kāi)我的世界服務(wù)器需要什么CPU，怎么樣？

手機(jī)怎么遠(yuǎn)程云主機(jī)名-云主機(jī)怎么遠(yuǎn)程操作？

Web技術(shù)的前世今生（一）

CSS基礎(chǔ)-如何用border寫三角形？

切圖崽的自我修養(yǎng)－優(yōu)化圖片加載流程

html5之canvas

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

每日一算法之冒泡排序

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！