拆分冒泡排序的算法與實現

王 瑜

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

數據結構教材中介紹了幾種序列的排序方法，其中快速排序和冒泡排序是兩種較長用的排序方法，這兩種方法各有特點.對于不同的問題，不同的方法有各自的優勢，排序方法選擇得當與否直接影響程序執行的速度和輔助存儲空間的占用量，進而影響整個軟件的性能[1].

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

1.1 快速排序法

快速排序的基本思想是從要被排序的序列R[1……n]中選定一個記錄作為“基準”關鍵字，從待排序列的兩端交替地向中間掃描，將其他記錄的關鍵字k'與k進行比較，若k'k，則將對應記錄換到R之后.通過一趟排序將待排序記錄分成兩部分，排在R之前的記錄的關鍵字均小于等于k，排在R之后的記錄的關鍵字均大于等于k；然后繼續對R前后兩部分記錄進行快速排序，直至排序范圍是1為止.

1.2 冒泡排序法

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

1.3 兩種排序方法的比較

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

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

2 拆分冒泡排序

2.1 算法基本思想

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

2.2 算法實現

#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) //排序函數

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指向元素的下標

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]

{/*交換數組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 算法分析

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

3 結束語

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

[1]余祥寶，崔國華，鄒海明.計算機算法基礎[M].武漢：華中科技大學出版社，2006.

[2]譚浩強，等.C程序設計[M]．北京：清華大學出版社，2001.

[3]連順金.快速排序的一種改進算法[J].三明學院學報，2009(04).