© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
冒泡排序算法及其改进
Ξ
周秋芬
(新乡市第二十二中学,河南新乡453000)

摘　要:传统的冒泡排序算法存在效率不高的缺陷。经过深入分析论证,提出了改进的方法,并编程予以实现
,

由此提高了算法的效率。
关键词:冒泡排序;算法;效率;编程
中图分类号:TP301.6 文献标识码:A 文章编号:1672Ο3325(2009)03Ο0160Ο
02

作者简介:周秋芬(1973Ο),女,河南新乡人,硕士,中学一级教师。研究方向:现代教育技术。

在众多的排序方法中,冒泡排序(bubblesort)是最简单的一种。这里主要对冒泡排序算法及其改进算法的基本原理进行介绍和分析,并对它们的算法性能进行分析。一、冒泡排序(一)基本思想将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。(二)排序过程1.比较第一个数与第二个数,若为逆序a[0]>a[1],则交换;然后比较第二个数与第三个数;依次类推,直至第n-1个数和第n个数比较为止。第一趟冒泡排序,结果最大的数被安置在最后一个元素位置上。2.对前n-1个数进行第二趟冒泡排序,结果使次大的数被安置在第n-1个元素位置。3.重复上述过程,共经过n-1趟冒泡排序后,排序结束。例:假设n=8,数组R中8个关键字分别为(53,36,48,36,60,17,18,41)用冒泡排序法进行排序。初始化关键字5336483660171841第一趟排序后3648365317184160第二趟排序后36364817184153第三趟排序后363617184148第四趟排序后3617183641第五趟排序后17183636第六趟排序后
171836

第七趟排序后
1718

(三)
算法实现

#includemain
()
{inta[11],i,j,t;
printf(”Input10numbers:\n”);
for(i=1;i<11;i++
)
scanf(“%d”,&a[i]);
printf(“\n”);
for(j=1;j<=9;j++
)
for(i=1;i<=10-j;i++
)
if(a[i]>a[i+1]
)
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
printf(“Thesortednumbers:\n”);
for(i=1;i<11;i++
)
printf(“%d”,a[i]);}
(四)
算法分析

1.
算法的最好时间复杂度。若文件的初始状态
是正序的,一趟扫描即可完成排序。所需的关键字
比较次数C和记录移动次数M均达到最小值
:Cmin

=n-1,Mmin=0。冒泡排序最好的时间复杂度为O
(n)
。

2.
算法的最坏时间复杂度。若初始文件是反序
的,需要进行n-1趟排序。每趟排序要进行
n-i

次关键字的比较(1≤i≤n-1),且每次比较都必须
移动记录三次来达到交换记录位置。在这种情况
下,比较和移动次数均达到最大值:Cmax=n(n-1)Π
2=O(n2),Mmax=3n(n-1)Π2=O(n2
)
。冒泡排序

的最坏时间复杂度为O(n2)。
3.算法的平均时间复杂度为O(n2
)
。虽然冒泡

排序不一定要进行n-1趟,但由于它的记录移动次

061

第22卷第3期新乡教育学院学报2009年9月
Vol.22,No.3JOURNALOFXINXIANGEDUCATIONCOLLEGESEP,2009
　

Ξ
　收稿日期:2009Ο05Ο
19
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

数较多,故平均时间性能比直接插入排序要差得多。4.算法稳定性。冒泡排序是就地排序,且它是稳定的。二、改进的冒泡排序(一)不出现交换就结束[1]1.算法思想在冒泡排序过程中,一旦发现某一趟没有进行交换操作,就表明此时待排序记录序列已经成为有序序列,冒泡排序再进行下去已经没有必要,应立即结束排序过程。可以用一个布尔变量来记录内循环是否进行了记录交换,如果没有则终止外循环。2.算法实现Bubblesort1(inta[],intn)ΠΠ数组a是待排序文件,n为数组中元素的个数{inti,j,k;intt;k=1;i=n-1;while(k){k=0;for(j=0;ja[j+1].key){t=a[j];a[j]=a[j+1];a[j+1]=t;k=1;}i--;　}}3.排序过程初始化关键字5336483660171841第一趟排序后3648365317184160第二趟排序后36364817184153第三趟排序后363617184148第四趟排序后3617183641第五趟排序后171836364.算法分析从冒泡排序的过程可以看出,如果在某一趟排序过程中,不出现交换,则说明每两个记录关键字进行比较时,都已不符合交换条件,即对升序排序来说,每对相邻的记录中的前一个记录的关键字都已比后一个记录的关键字小(a[j].key在一端冒泡的同时在另一端也进行冒泡,即反向冒
泡。这样就得到双向冒泡排序算法。
2.
算法实现
voiddoubleBubblesort(inta[],intn
)
ΠΠ数组a为存放待排数据的数组,n为数组a中

元素的个数
{inti,t,k1,h;
k1=0;h=n-1;
t=k1;
do{for(i=k1;i)
if(a[i].key>a[i+1].key
)
{k=a[i];a[i]=a[i+1];a[i+1]=k;t=i;}
h=t;
for(i=h;i>=k1;i--
)
if(a[i].key>a[i+1].key
)
{k=a[i];a[i]=a[i+1];a[i+1]=k;t=i;}
k1=t;
}while(k1}
3.
排序过程
初始化关键字
5336483660171841

第一趟排序后
1736483653184160

第二趟排序后
1718363648415360

第三趟排序后
1718363641485360

4.
算法分析
双向冒泡排序算法是原地置换算法
[2]
,并且a

[I].key>a[I+1].key时才进行交换,
所以说该算
法也是稳定的排序法。但如果改为a[I].key〉
=a[I

+1].key时才进行交换,
则改变其的稳定性
[3]
。该

算法在执行一趟排序后同时确定两个记录的位置
,

即待排区域的最大和最小的记录,上述其他算法在
执行一趟排序后仅能确定一个记录的位置,即最大
或最小的,显然该算法更可取。
三、结束语
笔者提出了两种新的排序方法,分析上面的程
序段可以发现:对于基本有序的问题通过增加逻辑
变量可以控制循环次数;对于基本无序的问题可以
采用双向冒泡的方法控制循环次数,从而起到了优
化冒泡法的作用。
参考文献
:

[1]张锦祥.冒泡排序及其改进算法[J].计算机时代,2002
(9)
.

[2]赵永杰,郭永利.冒泡排序算法的改进[J].文教资料,
2005(29).
[3]AnanyLevitin.算法设计与分析基础(影印版)[M].北京:
清华大学出版社
,2003:366-367.

【责任编校　李　敬】

161