9.3.2?冒泡排序算法

我們來(lái)看看正宗的冒泡算法，有沒(méi)有什么改進(jìn)的地方。/* 對(duì)順序表L作冒泡排序 */void BubbleSort(SqList *L){ int i,j;for(i=1;i<L->length;i++){for(j=L->length-1;j>=i;j--) /* 注意j是從后往前循環(huán) */{if(L->r[j]>L->r[j+1]) /* 若前者大于后者（注意這里與上一算法差異）*/{swap(L,j,j+1); /* 交換L->r[j]與L->r[j+1]的值 */}}}}

?? 依然假設(shè)我們待排序的關(guān)鍵字序列是{9,1,5,8,3,7,4,6,2}，當(dāng)i=1時(shí)，變量j由8反向循環(huán)到1，逐個(gè)比較，將較小值交換前面，直到最后找到最小值放置在了第1的位置。如圖9-5-3，當(dāng)i=1，j=8時(shí)，我們發(fā)現(xiàn)6>2，因此交換了它們的位置，j=7時(shí)，4>2，所以交換……直到j(luò)=2時(shí)，因?yàn)?<2，所在不交換。j=1時(shí)，9>1，交換，最終得到最小值1放置第一的位置。事實(shí)上，在不斷循環(huán)的過(guò)程中，除了將關(guān)鍵字1放到第一的位置，我們還將關(guān)鍵字2從第九位置提到到了第三的位置，顯然這一算法比前面的要有進(jìn)步，在上十萬(wàn)條數(shù)據(jù)的排序過(guò)程中，這種差異會(huì)體現(xiàn)出來(lái)。圖中較小的數(shù)字如同氣泡般慢慢浮到上面，因此就將此算法命名為冒泡算法。

?
??????? 當(dāng)i=2時(shí)，變量j由8反向循環(huán)到2，逐個(gè)比較，在將關(guān)鍵字2交換到第二位置的同時(shí)，也將關(guān)鍵字4和3有所提升。
?

?

??????? 后面的數(shù)字變換很簡(jiǎn)單，這里就不在贅述了。

9.3.3?冒泡排序優(yōu)化
??????? 這樣的冒泡程序是否還可以優(yōu)化呢？答案是肯定的。試想一下，如果我們待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是說(shuō)，除了第一和第二的關(guān)鍵字需要交換外，別的都已經(jīng)是正常的順序。當(dāng)i=1時(shí)，交換了2和1，此時(shí)序列已經(jīng)有序，但是算法仍然不依不饒的將i=2到9，以及每個(gè)循環(huán)中的j循環(huán)都執(zhí)行了一遍，盡管并沒(méi)有交換數(shù)據(jù)，但是之后的大量比較還是大大的多余了。

?

?

??????? 當(dāng)i=2時(shí)，我們已經(jīng)對(duì)9與8，8與7，……，3與2作了比較，沒(méi)有任何數(shù)據(jù)交換，這就說(shuō)明此序列已經(jīng)有序，不需要再繼續(xù)后面的循環(huán)判斷工作了。為了實(shí)現(xiàn)這個(gè)想法，我們需要改進(jìn)一下代碼，增加一個(gè)標(biāo)記變量flag，來(lái)實(shí)現(xiàn)這一算法的改進(jìn)。

/* 對(duì)順序表L作改進(jìn)冒泡算法 */void BubbleSort2(SqList *L){ int i,j;Status flag=TRUE; /* flag用來(lái)作為標(biāo)記 */for(i=1;i<L->length && flag;i++) /*若flag為true則有過(guò)數(shù)據(jù)交換，否則退出循環(huán)*/{flag=FALSE; /* 初始為false */for(j=L->length-1;j>=i;j--){if(L->r[j]>L->r[j+1]){swap(L,j,j+1); /* 交換L->r[j]與L->r[j+1]的值 */flag=TRUE; /* 如果有數(shù)據(jù)交換，則flag為true */}}}}

??????? 代碼改動(dòng)的關(guān)鍵就是在i變量的for循環(huán)中，增加了對(duì)flag是否為true的判斷。經(jīng)過(guò)這樣的改進(jìn)，冒泡排序在性能上就有了一些提升，可以避免因已經(jīng)有序的情況下的無(wú)意義循環(huán)判斷。

9.3.4?冒泡排序復(fù)雜度分析
??????? 分析一下它的時(shí)間復(fù)雜度。當(dāng)最好的情況，也就是要排序的表本身就是有序的，那么我們比較次數(shù)，根據(jù)最后改進(jìn)的代碼，可以推斷出就是n-1次的比較，沒(méi)有數(shù)據(jù)交換，時(shí)間復(fù)雜度為O(n)。當(dāng)最壞的情況，即待排序表是逆序的況，此時(shí)需要比較?次，并作等數(shù)量級(jí)的記錄移動(dòng)。因此，總的時(shí)間復(fù)雜度為O(n²)。

出處：http://www.cnblogs.com/cj723/archive/2011/04/15/2016689.html

總結(jié)

以上是生活随笔為你收集整理的《大话数据结构》第9章 排序 9.3 冒泡排序（下）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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