拆分冒泡排序的算法与实现

王 瑜

(安徽广播电视大学，安徽 合肥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).