冒泡排序的算法分析與改進(jìn)

1、冒泡排序的算法分析與改進(jìn)交換排序的基本思想是： 兩兩比較待排序記錄的關(guān)鍵字， 發(fā)現(xiàn)兩個(gè)記錄的次 序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。應(yīng)用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。 冒泡排序1、排序方法 將被排序的記錄數(shù)組R1.n 垂直排列，每個(gè)記錄 Ri 看作是重量為Ri.key 的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡， 就使其向上 飄浮 。如此反復(fù)進(jìn)行， 直到最后任 何兩個(gè)氣泡都是輕者在上，重者在下為止。(1) 初始R1.n 為無序區(qū)。(2) 第一趟掃描 從無序區(qū)底部向上依次比較相鄰的兩個(gè)氣泡的重量， 若發(fā)現(xiàn)輕者在下、 重

2、者 在上，則交換二者的位置。即依次比較(Rn , Rn-1) , (Rn-1 , Rn-2),， (R2 ， R1) ；對(duì)于每對(duì)氣泡 (Rj+1 ， Rj) ，若 Rj+1.key第一趟掃描完畢時(shí)， 最輕的氣泡就飄浮到該區(qū)間的頂部， 即關(guān)鍵字最小的 記錄被放在位置R1上。(3) 第二趟掃描掃描R2.n。掃描完畢時(shí)，次輕的氣泡飄浮到R2的位置上 最后，經(jīng)過 n-1 趟掃描可得到有序區(qū) R1.n第i趟掃描時(shí)，R1.i-1和Ri.n分別為當(dāng)前的有序區(qū)和無序區(qū)。掃描 仍是從無序區(qū)底部向上直至該區(qū)頂部。 掃描完畢時(shí)， 該區(qū)中最輕氣泡飄浮到頂部 位置 Ri 上，結(jié)果是 R1.i 變?yōu)樾碌挠行騾^(qū)。2、冒泡排

3、序過程示例對(duì)關(guān)鍵字序列為xxxX勺文件進(jìn)行冒泡排序的過程【參見動(dòng)畫演示】3、排序算法(1 )分析因?yàn)槊恳惶伺判蚨际褂行騾^(qū)增加了一個(gè)氣泡， 在經(jīng)過 n-1 趟排序之后， 有序 區(qū)中就有 n-1 個(gè)氣泡，而無序區(qū)中氣泡的重量總是大于等于有序區(qū)中氣泡的重量， 所以整個(gè)冒泡排序過程至多需要進(jìn)行 n-1 趟排序。若在某一趟排序中未發(fā)現(xiàn)氣泡位置的交換， 則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序后終止。 為此，在下面給出的算法中，引入一個(gè)布爾量exchange,在每趟排序開始前，先將其置為FALSE若排序過程中發(fā)生了交換，則將其置為TRUE各趟排序結(jié)束 時(shí)

4、檢查exchange，若未曾發(fā)生過交換則終止算法，不再進(jìn)行下一趟排序。(2)具體算法 voidBubbleSort(SeqListR) /R (I., n)是待排序的文件，采用自下向上掃描，對(duì)R做冒泡排序inti ， j ；BooIeanexchange； / 交換標(biāo)志for(i=1;iexchange=FALSE；/ 本趟排序開始前，交換標(biāo)志應(yīng)為假for(j=n-1;j=i；j-)/ 對(duì)當(dāng)前無序區(qū) Ri.n 自下向上掃描if(Rj+1.keyR0=Rj+1 ；/R0 不是哨兵，僅做暫存單元Rj+1=Rj ；Rj=R0 ；exchange=TRUE；/ 發(fā)生了交換，故將交換標(biāo)志置為真if(!e

5、xchange)/ 本趟排序未發(fā)生交換，提前終止算法return ；/endfor( 外循環(huán) )/BubbIeSort4、算法分析( 1)算法的時(shí)間復(fù)雜度若文件的初始狀態(tài)是正序的， 一趟掃描即可完成排序。 所需的關(guān)鍵字比較次 數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值：Cmin=n-1Mmin=0。冒泡排序的時(shí)間復(fù)雜度為 O(n) 。(2)算法的最壞時(shí)間復(fù)雜度若初始文件是反序的， 需要進(jìn)行 n-1 趟排序。每趟排序要進(jìn)行 n-i 次關(guān)鍵字 的比較(1 i n-1)，且每次比較都必須移動(dòng)記錄三次來達(dá)到交換記錄位置。在 這種情況下，比較和移動(dòng)次數(shù)均達(dá)到值：Cmax=n(n-1)/2=O(n2)Mmax=3n

6、(n-1)/2=O(n2)冒泡排序的最壞時(shí)間復(fù)雜度為 O(n2) 。(3)算法的平均時(shí)間復(fù)雜度為 O(n2)雖然冒泡排序不一定要進(jìn)行 n-1 趟，但由于它的記錄移動(dòng)次數(shù)較多， 考試大 提示平均時(shí)間性能比直接插入排序要差得多。(4) 算法穩(wěn)定性冒泡排序是就地排序，且它是穩(wěn)定的。5、算法改進(jìn)上述的冒泡排序還可做如下的改進(jìn)：(1) 記住最后一次交換發(fā)生位置 lastExchange 的冒泡排序 在每趟掃描中，記住最后一次交換發(fā)生的位置 lastExchange ，(該位置之前 的相鄰記錄均已有序) 。下一趟排序開始時(shí)， R1.lastExchange-1 是有序區(qū)， RlastExchange.n 是無序區(qū)。這樣，一趟排序可能使當(dāng)前有序區(qū)擴(kuò)充多個(gè)記錄， 從而減少排序的趟數(shù)。具體算法【參見習(xí)題】 。(2) 改變掃描方向的冒泡排序 冒泡排序的不對(duì)稱性 能一趟掃描完成排序的情況：只有最輕的氣泡位于 Rn 的位置，其余的氣 泡均已排好序，那么也只需一趟掃描就可以完成排序。【例】對(duì)初始關(guān)鍵字序列 12，18，42，44，45，67，94，10 就僅需一趟掃 描。需要 n-1 趟掃描完成排序情況：當(dāng)只有最重的氣泡位于 R1 的位置，其余的氣泡均已排好序時(shí)，則仍需做 n-1 趟掃描才能完成排序?！纠繉?duì)初始關(guān)鍵字序列： 94，10，12， 18，42，44