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

設(shè)數(shù)組長度為N。

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

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

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

?

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

[cpp]?view plaincopy

//冒泡排序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]);??

}??

下面對其進行優(yōu)化，設(shè)置一個標志，如果這一趟發(fā)生了交換，則為true，否則為false。明顯如果有一趟沒有發(fā)生交換，說明排序已經(jīng)完成。

[cpp]?view plaincopy

??

[cpp]?view plaincopy

//冒泡排序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--;??

???????}??

}??

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

[cpp]?view plaincopy

//冒泡排序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;??

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

????}??

}??

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

總結(jié)

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

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