眾所周知，冒泡排序是比較簡單并別比較經(jīng)典的排序算法，時間復(fù)雜度為O(n2).他的原理就是相鄰元素互相比較，如果前者比后者大，那么交換位置，然后進行下一步比較，第一輪之后，最大值就會跑到最后邊去。

例如有如下一個數(shù)組。 {10,12,5,24,38,26,14,2}

10

12

5

24

38

26

14

2

第一次循環(huán)：

1.10和12比，不動；12和5比，交換位置

10

5

12

24

38

26

14

2

2.然后12和24比，不動；24和38比，不動；38和26比，交換位置

10

5

12

24

26

38

14

2

3.然后38和14比，交換位置

10

5

12

24

26

14

38

2

4.最后38和2比，交換位置

10

5

12

24

26

14

2

38

到這里，第一次冒泡就結(jié)束了，可以看到38是最大值，它已經(jīng)跑到了最后，同理，進行

第2次（8-6）循環(huán)結(jié)果如下（26跑到了最后）：

10?

5

12

24

14

2

26

38

第3次(比較了8-3次)

10

5

12

14

2

24

26

38

第四次（比較了8-4次）

10

5

12

2

14

24

26

38

第五次（比較了8-5次）

10

5

2

12

14

24

26

38

第六次（比較了8-6次）

5

2

10

12

14

24

26

38

第七次（比較了8-7次）

2

5

10

12

14

24

26

38

第八次（不用循環(huán)了，只剩下最后一個值了，肯定是最小了）總共用了7次大循環(huán)，根據(jù)上圖可以得出每次小循環(huán)的次數(shù)是總長度減去循環(huán)次數(shù)，因為之前最大值已經(jīng)在最后，所以在比較就無意義。那么這個過程轉(zhuǎn)換為代碼如下。

.NET版本

//此段代碼已經(jīng)過?VS2012編程環(huán)境驗證for?(int?i?=?0;?i?<?sortArr.Length?-?1;?i++)?//?索引從?0?開始，所以長度減一{for?(int?j?=?0;?j?<?sortArr.Length?-?1?-?i;?j++)?//長度減一之后在減去i就是每次的小循環(huán)次數(shù){if?(sortArr[j]?>?sortArr[j?+?1])?//如果大于就換位置{temp?=?sortArr[j];sortArr[j]?=?sortArr[j?+?1];sortArr[j?+?1]?=?temp;}}} //當(dāng)然也有人這么寫?就是第二個循環(huán)不減去?i，其實也正確，只不過效率不如上邊的代碼高一些，不減的話會做些無意義的比較。大循環(huán)?長度不減1同理

Objective-C版本(代碼未驗證，讀者可自行實驗，原理相通)

//核心代碼?NSMutableArrar?*?sortArr for?(int?i?=?0;?i?<?[sortArr?count];?i++)?//?索引從?0?開始，所以長度減一{for?(int?j?=?0;?j?<?[sortArr?count]?-?1?-?i;?j++)?//長度減一之后在減去i就是每次的小循環(huán)次數(shù){NSInteger?a1?=?[[sortArr?objectAtIndex:?j]?intValue];NSInteger?a2?=?[[sortArr?objectAtIndex:?j+1]?intValue];if(a1?>?a2){[sortArr?exchangeObjectAtIndex:j?withObjectAtIndex:j+1];}}}

好了，到這里就是最基本的冒泡排序算法實現(xiàn)了，當(dāng)然還有各種優(yōu)化，面試過程中經(jīng)常見到冒泡排序，你寫出這段代碼，基本上就算過了。（看面試官的心情啦~）

轉(zhuǎn)載于:https://blog.51cto.com/panzi/1637040

總結(jié)

以上是生活随笔為你收集整理的研究研究冒泡排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。