冒泡排序算法的分析與改進(jìn) 算法設(shè)計.doc

算法分析論文冒泡排序算法的分析與改進(jìn)孫偉（安徽中醫(yī)學(xué)院 醫(yī)藥信息工程學(xué)院 09醫(yī)軟一班，安徽合肥，230009）摘 要： 冒泡排序算法有兩個優(yōu)點：1“編程復(fù)雜度”很低，很容易寫出代碼；2.具有穩(wěn)定性，這里的穩(wěn)定性是指原序列中相同元素的相對順序仍然保持到排序后的序列，但當(dāng)需要排序的數(shù)據(jù)較多且無序時，冒泡排序算法的時間復(fù)雜度較大，比較次數(shù)較多，本文提出了一種冒泡排序算法的改進(jìn)方法，可以大大減少比較的次數(shù)，降低算法的時間復(fù)雜度。關(guān)鍵詞：交換排序 掃描 穩(wěn)定 算法中圖分類號：TU 411.01 文獻(xiàn)標(biāo)識碼：A Bubble sort algorithm analysis and improvementSUN Wei(Anhui University of Traditional Chinese Medicine Medical Information Engineering, Hefei 230009, China；)Abstract: Bubble sort algorithm has two advantages:1 “Programming complexity”is very low，and it is easy to write code;2.It has the stability, the stability refers to the original sequence in the same element relative sequence remains to sort sequence, but when the need to sort the data and more disordered, bubble sort algorithm time complexity compared to larger, more often, this paper presents a bubble sort algorithm method, can greatly reduce the number of comparisons, reduce the time complexity of algorithm.Key words：Exchange sort ; Scanning ; stability ; Algorithm收稿日期：2012-4-14；作者簡介：孫偉 1992-10-04 女 09713033 09醫(yī)軟一班 算法分析論文 1.概述1.1 冒泡排序簡介冒泡排序法是一種交換排序法，這種方法的基本思想是，將待排序的元素看作是豎著排列的“ 氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“ 氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即“ 輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“ 最輕”的元素就浮到了最高位置；處理二遍之后，“ 次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“ 最輕”元素，所以不必檢查。一般地，第i 遍處理時，不必檢查第i 高位置以上的元素，因為經(jīng)過前面i- 1遍的處理，它們已正確地排好序。1.2 冒泡排序方法冒泡排序法是一種最簡單的排序算法,它和氣泡從水中往上冒的情況有些類似。其基本算法如下：對1 至n 個記錄，先將第n 個和第n- 1 個記錄的鍵值進(jìn)行比較，如rn.keyrn- 1.key,則將兩個記錄交換。然后比較第n- 1 個和第n- 2 個記錄的關(guān)鍵字； 依次類推， 直到第2 個記錄和第1 個記錄進(jìn)行比較交換，這稱為一趟冒泡。這一趟是所實現(xiàn)的功能：將鍵值最小的記錄傳到了第1 位。然后，再對2 至n 個記錄進(jìn)行同樣操作，則具有次小鍵值的記錄被安置在第2 位上。重復(fù)以上過程， 每次的移動都向最終排序的目標(biāo)前進(jìn)，直至沒有記錄需要交換為止。具體實現(xiàn)時，可以用一支旗子flag 表示第i 趟是否出現(xiàn)交換。如果第i 趟沒有交換，則表示此時已完成排序，因而可以終止。1.3 冒泡排序過程示例設(shè)待排序的鍵值為：25 17 65 13 94 47 41 94執(zhí)行冒泡排序的過程如下圖所示。其中，第一列為初始鍵值序列,第二列至第八列依次為各趟排序的結(jié)果， 圖中用方括號括起來的是當(dāng)前待排序的無序區(qū)。每一次排序都使有序區(qū)擴(kuò)充了一個氣泡，在經(jīng)過i 次排序之后，有序區(qū)中就有i 個氣泡， 而無序區(qū)中氣泡的重量總是大于等于有序區(qū)中氣泡的重量，整個冒泡排序過程至多需要進(jìn)行n- 1 次排序。但是,若在某一次排序中未發(fā)現(xiàn)氣泡位置的交換， 則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則因此冒泡排序過程可在此次排序后終止。在上圖的示例中，在第四次(圖中第五列)排序過程中就沒有氣泡交換位置,此時整個文件已達(dá)到有序狀態(tài)。為此，實際給出的算法中， 我們可以引入一個布爾量flag， 在每一次排序之前， 先將它置為true，若在一次排序中交換了記錄,則將它置為false。當(dāng)一次排序結(jié)束時，我們再檢查flag，若未曾交換過記錄便終止算法。該算法的時間復(fù)雜性為0(n2),算法為穩(wěn)定的排序方法。2.對于冒泡算法的改進(jìn)2.1 第一種改進(jìn)方法如果在某一趟循環(huán)中沒有任何數(shù)據(jù)交換發(fā)生， 則表明數(shù)據(jù)已經(jīng)排序完畢。那么剩余的循環(huán)就不需要再執(zhí)行假設(shè)需要排序的數(shù)據(jù)已經(jīng)按照從小到大排列，那么第一趟比較就不會有任何數(shù)據(jù)交換發(fā)生。這種改進(jìn)算法如下：設(shè)置一個標(biāo)志位，當(dāng)沒有交換的時候這個標(biāo)志位不會變化，那么說明數(shù)據(jù)已經(jīng)排序好了，就不需要再進(jìn)行剩余的循環(huán)。只有在標(biāo)志位被重新設(shè)置的情況下才會進(jìn)行剩余的循環(huán)。publicstaticvoid ImproveBubble1(int myArray)bool isSorted = false;for(int i = 0; i myArray.Length - 1 &!isSorted; i+)/ 只有在沒有排序的情況下才繼續(xù)循環(huán) isSorted =true; / 設(shè)定排序標(biāo)志for(int j = 0; j myArrayj+1 ) isSorted =false; / 如果是沒有排序，就重新設(shè)定標(biāo)志Swap(refmyArray, refmyArrayi+1);從這種算法可以看出，若記錄的初始狀態(tài)是正序（ 從小到大） 的，則一趟掃描即可完成排序。所需的較和記錄移動的次數(shù)分別達(dá)到最小值n- 1 和0。即算法最好的時間復(fù)雜度為0(n)；若初始記錄是反序（ 從大到?。?的，則需要進(jìn)行n- 1 趟排序，每趟排序要進(jìn)行n- i 次關(guān)鍵字的比較，且每次比較都必須移記錄三次來達(dá)到交換記錄位置。在這情況下比較和移動次數(shù)達(dá)到最大值：比較次數(shù)：Cmax= n(n- 1)/2 移動次數(shù)： Mmax=3n(n- 1)/2因此這種改進(jìn)方法的最壞時間復(fù)雜度也為0(n2)。在平均情況下，算法可能在中間的某一趟排序完后就終止，但總的比較次數(shù)仍為0(n2)，所以算法的平均時間復(fù)雜度為0(n2)。因此，這種算法最好的時間復(fù)雜度為0(n)。平均，最壞時刻復(fù)雜度為0(n2)。2.2 第二種改進(jìn)方法在冒泡排序的每趟掃描中， 記住最后一次交換發(fā)生的位置lastexchange也能有所幫助。因為該位置之前的相鄰記錄已經(jīng)有序，故下一趟排序開始的時候，0 到lastexchange 已經(jīng)是有序的了，lastexchange 到n- 1是無序區(qū)。所以一趟排序可能使當(dāng)前有序區(qū)擴(kuò)充多個記錄。即較大縮小無序區(qū)范圍，而非遞減1，以此減少排序趟數(shù)。這種算法如下：在冒泡排序中，每趟排序?qū)崿F(xiàn)了將最大(升序)或最小(降序)的記錄安置到未排序部分的最后位置，即最終位置。通過進(jìn)一步觀察研究，由于每趟排序過程中，通過和鄰記錄關(guān)鍵字兩兩比較，大(升序)或小(降序)的記錄在不斷地往下沉或往后靠，小(升序)或大(降序)的記錄在不斷往上冒或往前靠。每經(jīng)過一趟排序，在最后次交換位置后面的記錄都已經(jīng)排好序。根據(jù)上面的思路，對n 個記錄進(jìn)行第k 趟排序，首先需在第k- 1 趟排序時記下最后交換的位置。然后在第k 趟排序時，將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比較，符合交換條件時，進(jìn)行交換。再比較第二個記錄和第三個記錄的關(guān)鍵字，依次類推，直至第m- 1 個記錄和第m 個記錄的關(guān)鍵字進(jìn)行比較，而不需要比較至n- k- 1 個記錄。在大部分排序中，m 都小于n- k- 1從而減少了比較趟數(shù)和每趟的比較次數(shù)。由于在第一趟排序時，沒有上一趟排序的m 值。因此，還要設(shè)置m 的初始值為n- 1。publicstaticvoid ImproveBubble2(int myArray) int m= myArray.Length -1;int k, j;while(m 0 ) for( k=j=0; jmyArrayj+1)Swap(refmyArrayj, refmyArrayj+1);k = j; / 記錄每次交換的位置m= k; / 記錄最后一個交換的位置從這種算法可以看出，若記錄的初始狀態(tài)是正序（ 從小到大） 的。則一趟掃描即可完成排序， 所的關(guān)鍵比較和記錄移動的次數(shù)分別達(dá)到最小值n- 1 和0。即算法最好的時間復(fù)雜度為0(n);若初始記錄是反序（ 從大到?。?的，則需要進(jìn)行n- 1 趟排序，每趟排序要進(jìn)行n- i 次關(guān)鍵字的比較，且每次比較都須移動記錄三次來達(dá)到交換記錄位置。在這情況下比較和移動次數(shù)達(dá)到最大值：比較次數(shù)：Cmax= n(n- 1)/2 移動次數(shù)Mmax=3n(n- 1)/2因此，這種辦法的最壞時間復(fù)雜度也為0(n2)。在平均情況下，算法較大地改變了無序區(qū)的范圍，從而減少了比較的次數(shù)，但總的比較次數(shù)仍為0(n2)。所以算法的平均時間復(fù)雜度為0(n2)。因此，算法2 最好的時間復(fù)雜度為0(n)。平均，最壞時刻復(fù)雜度為0(n2)。2.3 雙向掃描冒泡法若記錄的初始狀態(tài)為:只有最輕的氣泡位于dn的位置(或者最重的氣泡位于d0位置)，其余的氣泡均已排好序。在上述三種算法中都要做n- 1 趟掃描。實際上只需一趟掃描就可以完成排序。所以對于這種不對稱的情況?？蓪γ芭菖判蛴肿饕淮胃倪M(jìn)。在排序過程中交替改變掃描方向。即先從下掃到上，再從上掃到下，來回地進(jìn)行掃描，這樣就得到雙向冒泡排序算法。對n 個記錄進(jìn)行排序時，設(shè)up 記錄了從前面向后面依次進(jìn)行掃描時最后的交換位置，low記錄了從后面向前面依次進(jìn)行掃描時最前的交換位置。由上個改進(jìn)的冒泡排序的原理可知，up 后面的記錄和low 前面的記錄都已有序。每趟排序都由兩次不同方向的比較、交換組成。第一次是從未排好序的第一個記錄開始，即從low 記錄開始，向后依次兩兩比較，如果不符合條件，則交換之，直至比較到未排好序的最后一個記錄，即up 記錄為止。同時記下最后一次交換的位置，并存于up。第二次是從未排好序的最后一個記錄開始,即從up 記錄開始，向前依次兩兩比較，如果不符合條件，則交換之，直至比較到未排好序的第一個記錄，即low記錄為止。同時記下最后次交換的位置，并存于low。這樣，就完成了一趟排序。每趟排序都實現(xiàn)了將未排好序部分的關(guān)鍵字大的記錄往后移(升序)，關(guān)鍵字小的記錄往前移（ 升序)，從而使兩端已排好序（ 如果是降序，記錄移動的方向則相反)。未排好序部分的記錄的首尾位置分別由low和up 指明。不斷按上面的方法進(jìn)行排序，使兩端已排好序的記錄不斷增多，未排好序部分的記錄逐漸減少。即low 和up 的值不斷接近，當(dāng)low=up 時，表明已沒有未排好序的記錄，排序就完成了。由于在第一趟排序時，沒有上趟排序的low和up 值。因此，還要設(shè)置low 和up 的初始值分別為0 和n- 1。publicstaticvoid ImproveBubble3(int myArray) int low, up, index, i;low= 0;up = myArray.Length - 1;index = low;while( up low) for( i=low; imyArrayi+1)Swap(refmyArray, refmyArrayi+1);index = i;up= index; / 記錄最后一個交換的位置for(i=up; ilow; i- - ) / 從最后一個交換位置處從下向上掃描 if(myArraymyArrayi- 1)Swap(refmyArray, refmyArrayi- 1);index = i; low= index; / 記錄最后一個交換的位置從這種算法可以看出，若記錄的初始狀態(tài)是正序（ 從小到大） 的，則一趟掃描即可完成排序。所需的關(guān)鍵比較和記錄移動的次數(shù)分別達(dá)到最小值n- 1 和0。即算法最好的時間復(fù)雜度為0(n);若初始記錄是反序（ 從大到?。?的，則需要進(jìn)行n/2趟排序。如果只有最重的氣泡在最上面（ 或者最輕的氣泡在最下面） ，其余的有序，這時候就只需要比較1 趟。但是在最壞的情況下，算法的復(fù)雜度也為0(n2)。因此，算法最好的時間復(fù)雜度為0(n)，最壞時刻復(fù)雜度為0(n2)。3.性能分析為了分析數(shù)據(jù)兩種冒泡排序法的性能， 我們用自編的測試程序?qū)Υ罅繑?shù)據(jù)進(jìn)行了測試，得出下表，從表中可以直觀地看出兩種冒泡排序方法的性能差異（ 時間單位為毫秒）。圖1 算法運行時間比較表4.結(jié)束語從上面的表格可以看出，在數(shù)據(jù)量比較小的時候，這幾種算法基本沒有任何區(qū)別。當(dāng)數(shù)據(jù)量比較大的時候，雙向掃描冒泡排序會有更好的效率。但是效率并沒有根本的提升。因此冒泡排序確實不是我們排序的首選。在數(shù)據(jù)量比較大的時候，快速排序等會有非常明顯的優(yōu)勢。