在教學(xué)中對冒泡排序算法的改進(jìn)

施祖平

(南通紡織職業(yè)技術(shù)學(xué)院，江蘇 南通226007)

1 引言

在數(shù)據(jù)結(jié)構(gòu)教學(xué)過程中，排序是一個很重要的教學(xué)內(nèi)容.排序作為數(shù)據(jù)處理中的一種重要運(yùn)算，其本質(zhì)是將一組數(shù)據(jù)元素的無序序列按一定的規(guī)律進(jìn)行重新排列，最終成為有序序列.在計算機(jī)處理排序時，花費(fèi)的時間較多，通過改進(jìn)排序算法來提高系統(tǒng)的工作效率是非常有效的.排序的方法有很多，本文就冒泡排序法的算法提出一個改進(jìn)的探討.

2 普通冒泡法

冒泡法排序：通過比較在待排數(shù)組中相鄰元素的值來進(jìn)行，如果這些元素的第一個值比第二個值大就交換兩個值，然后比較下一組相鄰元素的值，在包括N個數(shù)據(jù)項的待排序的數(shù)據(jù)中，這個比較過程從下標(biāo)1和下標(biāo)2開始直到下標(biāo)N-1和N元素為止，這就是一趟比較，其結(jié)果使最大的數(shù)據(jù)被安置到最后一個記錄的位置上.一趟結(jié)束后，重新進(jìn)行第二趟對N-1個數(shù)據(jù)進(jìn)行同樣的操作，其結(jié)果使次大的數(shù)據(jù)被安置到第N-1位置上.一般地講，第i趟冒泡排序是從a[1]到a[n-i]依次將其與其后相鄰的數(shù)據(jù)進(jìn)行比較，并在“逆序”時交換相鄰元素，結(jié)果使這n-i+1個數(shù)據(jù)中的最大元素被交換到第n-i+1的位置上，如此進(jìn)行m(1≤m≤n-1)趟比較，直到在某一趟比較中沒有任何一隊數(shù)組元素發(fā)生交換為止，在每一趟的比較交換過程中，總是使較大的元素向下沉，而較小的元素向上浮，這就好比水中的“氣泡”沉浮一樣，因此稱為冒泡排序法.

3 兩頭冒泡法

改進(jìn)原因：在普通冒泡法中有一種不對稱性無法解決，也就是說，如果最大的元素在首位置而其余的元素都已排好序，那么只進(jìn)行一趟冒泡就可以完成排序.例如，{19，10，11，12，13，14，15，16，17，18}就僅需一趟冒泡.而當(dāng)最小的元素位于末尾位置且其余元素都排好序時，則需要n-1趟冒泡才能完成排序.例如，待排序序列{11，12，13，14，15，16，17，18，19，10}就需要九趟冒泡.造成這種不對稱的原因是，每趟冒泡過程都能使較大的元素下沉最大距離到它應(yīng)到的最終位置，而較小的元素卻只能向上浮一個位置.如果我們改變冒泡過程的掃描方向，每趟從尾部向前掃描，那么情況正好相反.例如，待排序序列{19，10，11，12，13，14，15，16，17，18}就需要掃描九趟，而序列{11，12，13，14，15，16，17，18，19，10}就只需要掃描一趟.為改變上述兩種情況的不對稱性，我們可以改變掃描方向來實(shí)現(xiàn).

改進(jìn)方法：在排序過程中交替改變掃描方向，實(shí)行雙向排序，從而減少比較的次數(shù).通過減少關(guān)鍵字的比較次數(shù)，提高排序算法的執(zhí)行效率，達(dá)到優(yōu)化目的.也就是說，分別從兩頭交替掃描進(jìn)行冒泡排序，所以可以稱這種改進(jìn)的冒泡排序法為“兩頭冒泡法”.采用這種改進(jìn)的方法進(jìn)行排序時，以上兩個待排序序列最多就只需要掃描兩次就能完成排序了.

改進(jìn)程序：

/*兩頭冒泡法程序*/

#include

#define N 10

main()

{int i，j，t，f，m，a[N+1];

printf(“Enter data:/n”); /*輸入待排序數(shù)據(jù)*/

for (i=0;i

{printf(“a[%d]=”，i);

scanf(“%d”，&a[i]);

}

printf(“ The original numbers: ”); /*輸出排序前原始數(shù)據(jù)*/

for(i=1;i

printf(“%5d”，a[i]);

printf(“ ”);

m=0; /*m用來統(tǒng)計冒泡的趟數(shù)和計算下一冒泡位置*/

f=1;

i=1;

while (f) /*改進(jìn)處：進(jìn)行兩頭冒泡排序*/

{ f=0;

m++;

for (j=i;j

if(a[j]>a[j+1])

{t=a[j];

a[j]=a[j+1];

a[j+1]=t;

f=1;

}

for (j=N-1;j>=i+1;j--) /*逆向冒泡排序*/

if (a[j]

{t=a[j];

a[j]=a[j-1];

a[j-1]=t;

f=1;

}

i++;

}

printf (“The scaning is made %d times ”，m); /*輸出冒泡的趟數(shù)*/

printf (“ The sorted numbers: ”);

for (i=1;i

printf (“%5d”，a[i]);

}

4 結(jié)束語

冒泡排序法作為一種簡單而又實(shí)用的排序方法，受到大家的普遍喜歡和廣泛應(yīng)用，通過算法的改進(jìn)，能進(jìn)一步提高排序的效率.學(xué)生在學(xué)習(xí)過程中，對這種改進(jìn)的方法很感興趣，很多學(xué)生通過閱讀大量的程序，對其它的排序算法也進(jìn)行改進(jìn)的嘗試，學(xué)習(xí)主動性增強(qiáng)了.當(dāng)然，冒泡法作為一種常用的排序算法，同樣值得我們進(jìn)一步的研究和學(xué)習(xí)，以便在實(shí)際應(yīng)用過程中進(jìn)一步改進(jìn)和完善.

參考文獻(xiàn)：

[1]陳明.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程[M].北京：清華大學(xué)出版社，2007.

[2]徐士良.計算機(jī)常用.[M].北京：清華大學(xué)出版社，1995.

[3]Anany Levitin. 算法設(shè)計與分析基礎(chǔ)(影印版) [M]. 北京: 清華大學(xué)出版社，2003.