王 瑜

(安徽廣播電視大學(xué)，安徽 合肥230022)

數(shù)據(jù)結(jié)構(gòu)教材中介紹了幾種序列的排序方法，其中快速排序和冒泡排序是兩種較長用的排序方法，這兩種方法各有特點(diǎn).對于不同的問題，不同的方法有各自的優(yōu)勢，排序方法選擇得當(dāng)與否直接影響程序執(zhí)行的速度和輔助存儲空間的占用量，進(jìn)而影響整個(gè)軟件的性能[1].

1 快速排序法和冒泡排序法

1.1 快速排序法

快速排序的基本思想是從要被排序的序列R[1……n]中選定一個(gè)記錄作為“基準(zhǔn)”關(guān)鍵字，從待排序列的兩端交替地向中間掃描，將其他記錄的關(guān)鍵字k'與k進(jìn)行比較，若k'k，則將對應(yīng)記錄換到R之后.通過一趟排序?qū)⒋判蛴涗浄殖蓛刹糠?，排在R之前的記錄的關(guān)鍵字均小于等于k，排在R之后的記錄的關(guān)鍵字均大于等于k；然后繼續(xù)對R前后兩部分記錄進(jìn)行快速排序，直至排序范圍是1為止.

1.2 冒泡排序法

冒泡排序的基本思想是：將相鄰的兩個(gè)數(shù)據(jù)元素按關(guān)鍵字進(jìn)行比較，如果反序則交換.對于一個(gè)待排序的數(shù)據(jù)元素序列，經(jīng)一趟排序后最大值數(shù)據(jù)元素移到最大位置，其它值較大的數(shù)據(jù)元素也向最終位置移動，此過程為一次起泡.然后對下面的記錄重復(fù)上述過程直到過程中沒有交換為止，則已完成對記錄的排序[2].

1.3 兩種排序方法的比較

快速排序和冒泡排序的時(shí)間效率都與初始序列有關(guān)，對于快速排序而言，初始序列為向有序時(shí)的時(shí)間復(fù)雜度為O(n2)，無序情況下的時(shí)間復(fù)雜度為O(nlg2n)；而對于冒泡排序來說，初始序列為向有序時(shí)的時(shí)間復(fù)雜度為O(n)，在無序情況下的時(shí)間復(fù)雜度為O(n2).

通過比較可以認(rèn)為：當(dāng)初始序列無序時(shí)，使用快速排序的效率更高一些，處理有序性比較強(qiáng)的初始序列時(shí)，使用冒泡排序的效率更高.但是現(xiàn)實(shí)中的情況是很復(fù)雜的，假設(shè)需要對批量數(shù)組排序，它們的n值都很大，數(shù)組可能是有序或無序的，要求機(jī)器在有限的時(shí)間內(nèi)處理完畢.解決這個(gè)問題單純地使用快速排序或冒泡排序都不太合適，需要更有針對性的排序算法來處理.

2 拆分冒泡排序

2.1 算法基本思想

拆分冒泡排序是將快速排序有效地改變后再和冒泡排序結(jié)合使用的一種算法，它分成兩個(gè)過程進(jìn)行，它們是拆分過程和冒泡過程.拆分過程是快速排序的變異，把序列的均值作為“基準(zhǔn)”關(guān)鍵字，通過一次掃描將大于“基準(zhǔn)”關(guān)鍵字的記錄放在數(shù)組的左邊部分，小于基準(zhǔn)“關(guān)鍵字的記錄放在數(shù)組的右邊部分.用變量averae存儲序列記錄的均值，附設(shè)兩個(gè)指針p和q，它們的初值分別為R[0]和R[n-1].首先p從所指位置起后搜索，直至找到第一個(gè)關(guān)鍵字大于ave的元素R[a]，接著q從所指位置起向前搜索．直至找到第一個(gè)關(guān)鍵字小于ave的元素R[b]，然后R[a]和R[b]互相交換，重復(fù)以上步驟直至p≥q為止[3].注意，這個(gè)拆分過程只需要對序列掃描一次，一次掃描后的序列被p和q拆分成兩部分.最后q和p再定位到序列中大于ave和小于ave的邊界位置.冒泡過程是對被拆分為兩段的序列先后冒泡排序，由于前段記錄的關(guān)鍵字都是小于ave的，后段記錄的關(guān)鍵字都是大于ave的，因此兩段分別進(jìn)行冒泡排序后，整段序列一定是有序序列.

2.2 算法實(shí)現(xiàn)

#indude

#indude

main()

{int n， i;

int *array

printf(“請輸入序列的長度：/n”);

scanf(“%d”，&n);

array=(int *)malloc(n+1)*sizeo(int))

printf(“請輸入序列記錄：/n”);

for(i=1;i<=n;i++) scanf(“%d”，array+i);

printf(“ ”);

sort(array，n)

}

void sort (ar，m) //排序函數(shù)

int ar[ ]; int m;

{int i， j， t; c， flag;

int *p， *q， *a;

float ave， sum=ar[0];

for(i=0;i

{sum=sum+array[i];

ave=sum/m;} //求序列均值ave

p=&ar[0];q=&ar[n-1];c=n-1； //c的值始終是q指向元素的下標(biāo)

while(p

{ if(*p<=(int)ave) p++;

else if(*q>=(int)ave)

{q--; c--}

else {t=*p;*p=*q;*q=t}

}

if(p=q)

{if(*p<(int)ave) p++;

else q--;} //拆分序列

for(i=0;i

{flag=0;

for(j=c-1;j>i;j--)

if(ar[j]

{/*交換數(shù)組ar[j]和ar[j-1]*/

t=ar[j];

ar[j]=ar[j-1];

ar[j-1]=t;

flag=1;

}

if (flag=0) break;

}

for(i=c;i

{flag=0;

for(j=n-1;j>i;j--)

if(ar[j]

{t=ar[j];

ar[j]=ar[j-1];

ar[j-1]=t;

flag=1;

}

if (flag=0) break;

}

}

2.3 算法分析

經(jīng)分析，拆分冒泡排序的處理時(shí)間應(yīng)該是拆分過程耗時(shí)與兩次冒泡耗時(shí)之和，拆分過程的處理時(shí)間為求均值耗時(shí)與進(jìn)行一遍比較耗時(shí)之和，拆分過程的時(shí)間復(fù)雜度應(yīng)該是O(2n).初始序列為有序序列時(shí)，復(fù)雜度為O(2n)+2O(n/2)，初始序列處于無序狀態(tài)時(shí)的時(shí)間復(fù)雜度為O(2n)+2O(n2/4).與冒泡排序相比，拆分冒泡排序在處理無序序列時(shí)效率高很多，處理有序序列的耗時(shí)也只是多出兩次掃描的時(shí)間；與快速排序相比，雖然處理無序序列的耗時(shí)會多一些，但是避免了有序序列狀況下快速排序所作的大量空操作.

3 結(jié)束語

排序算法的性能分析和選擇是一個(gè)復(fù)雜而又實(shí)際的問題，沒有哪一種是絕對最優(yōu)的.拆分冒泡排序算法在特定情況下能保證高效執(zhí)行，但代表性并不強(qiáng)，大多數(shù)情況下人們習(xí)慣使用的還是一些基本的排序方法.

[1]余祥寶，崔國華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)[M].武漢：華中科技大學(xué)出版社，2006.

[2]譚浩強(qiáng)，等.C程序設(shè)計(jì)[M]．北京：清華大學(xué)出版社，2001.

[3]連順金.快速排序的一種改進(jìn)算法[J].三明學(xué)院學(xué)報(bào)，2009(04).