http://blog.csdn.net/morewindows/article/details/6657829?

?

冒泡排序是非常容易理解和實現，，以從小到大排序舉例：

設數組長度為N。

1．比較相鄰的前后二個數據，如果前面數據大于后面的數據，就將二個數據交換。

2．這樣對數組的第0個數據到N-1個數據進行一次遍歷后，最大的一個數據就“沉”到數組第N-1個位置。

3．N=N-1，如果N不為0就重復前面二步，否則排序完成。

?

按照定義很容易寫出代碼：

[cpp]??view plain??copy

//冒泡排序1??

void?BubbleSort1(int?a[],?int?n)??

{??

???????int?i,?j;??

???????for?(i?=?0;?i?<?n;?i++)??

??????????????for?(j?=?1;?j?<?n?-?i;?j++)??

?????????????????????if?(a[j?-?1]?>?a[j])??

????????????????????????????Swap(a[j?-?1],?a[j]);??

}??

下面對其進行優化，設置一個標志，如果這一趟發生了交換，則為true，否則為false。明顯如果有一趟沒有發生交換，說明排序已經完成。

[cpp]??view plain??copy

??

[cpp]??view plain??copy

//冒泡排序2??

void?BubbleSort2(int?a[],?int?n)??

{??

???????int?j,?k;??

???????bool?flag;??

??

???????k?=?n;??

???????flag?=?true;??

???????while?(flag)??

???????{??

??????????????flag?=?false;??

??????????????for?(j?=?1;?j?<?k;?j++)??

?????????????????????if?(a[j?-?1]?>?a[j])??

?????????????????????{??

????????????????????????????Swap(a[j?-?1],?a[j]);??

????????????????????????????flag?=?true;??

?????????????????????}??

??????????????k--;??

???????}??

}??

再做進一步的優化。如果有100個數的數組，僅前面10個無序，后面90個都已排好序且都大于前面10個數字，那么在第一趟遍歷后，最后發生交換的位置必定小于10，且這個位置之后的數據必定已經有序了，記錄下這位置，第二次只要從數組頭部遍歷到這個位置就可以了。

[cpp]??view plain??copy

//冒泡排序3??

void?BubbleSort3(int?a[],?int?n)??

{??

????int?j,?k;??

????int?flag;??

??????

????flag?=?n;??

????while?(flag?>?0)??

????{??

????????k?=?flag;??

????????flag?=?0;??

????????for?(j?=?1;?j?<?k;?j++)??

????????????if?(a[j?-?1]?>?a[j])??

????????????{??

????????????????Swap(a[j?-?1],?a[j]);??

????????????????flag?=?j;??

????????????}??

????}??

}??

冒泡排序畢竟是一種效率低下的排序方法，在數據規模很小時，可以采用。數據規模比較大時，最好用其它排序方法。?

轉載于:https://www.cnblogs.com/android-blogs/p/6344031.html

總結

以上是生活随笔為你收集整理的白话经典算法系列之一 冒泡排序的三种实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。