2006年2月 电 脑 学 习 第1期
冒泡排序的分析与改进
桂 斌
摘 要 从时间和空间角度全面地分析 了冒泡排序的思想和特点．在此善础上以记住最后一次交换发生位置改进了冒泡
排 序。
关键词 交换排序 冒泡排序 时间复杂度
中图分类号 TP311．11 文献标识码 B 文章编号 ：1002—2422(2Oo6)Ol一0o22—02
The Analysis and Improvement of Bubble Sorting
GlIi Bi“
Abstract The paper analyzes the idea and feature of bubbling sorting a8 for the timing and space．Based on them by rem—
embering the last exchanging position，the bubble sorting is improved．
Keyword Exchange Sorting Bubble So~ing Timing Complexity
我们知道交换排序的基本思想[- 是：两两比较待排序
记录的关键字，发现两个记录的次序相反时即进行交换，直
到没有反序的记录为止。应用交换排序基本思想的主要排
序方法有：冒泡排序[· 和快速排序[ 。这里我们主要介绍冒
泡排序。涉及算法均用c语言实现。
1排 序 方 法
将被排序的记录数组R[1--n]垂直排列，每个记录 R
[i]看作足重量为R[i]．key的气泡。根据轻气泡不能在重
气泡之 卜的原则，从 F往．．L扫描数组 R：凡扫描到违反本原
则的轻气泡，就使其向上”飘浮 。如此反复进行，直到最后
任何两个气泡都足轻者在上，重者在F为止。
1．1初始
R[1 ]为无序区。
1．2第一次扫描
从无序区底部向』：依次比较相邻的两个气泡的重量，
若发现轻者在下、重者在上，则交换二者的位置。即依次比
较 (R[n]，R[n一1])，(R In一1]，R[n一2])，⋯，(R
[2]，R[1])：对于每对气泡 (R[j+1]，R[j])．若 R i-j+
1]．key<R[j]．key，则交换R[j+1]和R[j]的内容。
第一次扫描完毕时， 最轻 的气泡就飘浮到该区间的顶
部，即关键字最小的记录被放在最高位置 R[1]一L。
1I3第二次扫描 ’
扫描 R [2．．n]。扫描完毕时，”次轻 的 t泡飘浮到 R
[2]的位置 }：⋯⋯
最后，经过n一1次扫描可得到有序区R[1__n]
注意：
第 i次扫描时，R[1．．i-1]和 R[i-．n]分别为当前的有
序区和无序区。扫描仍是从无序区底部向上直至该区项部。
扫描完毕时，该区中最轻气泡飘浮到顶部位置 R[i]上，结
End If
get session ( oPageEngine”)
oRpt )．1'ageEngine
End If
％> <／body>
=session(” 在 IE 显示水晶报表 <／html>
<!一一 #include file ： ”smartviewemetivex
asp --->
4结 束 语
本文介绍了参数化水品报表的Web实现原理和一般
程序结构。利刚 ASP和水晶报表开发基于 Web参数化的报
表应用程序，结构简单，使用方便，代码重复利月j性好，是丌
发企业信息系统的一种理想报表手段。
参 考 文 献
[1]李云亮，李耷H枢．．NET环境 卜两种 web报表解决方
案的埘比分析．成部：计算机应用研究，20o4，6：212~214
[2] 张能立．Web动态报表的实现．卜海：计算机应用与
软件，2004，21(4)：110—112．
[3] 冯华英等译．水晶报表Crystal Repoas 9从入f J到精
通．北京：电：f工业出版社，2003．
[4]精英科技．ASP核心技术．北京：中国电力m版社，
20o1．
[5]廖信彦．Active Server Pages3．0彻底研究．北京：中
国铁道出版社，2000
}杜斌 江苏省淮阴师范学院信息传播 技术系助教(淮安 223001) 收稿日期：2005-09-27
· 22 ·
维普资讯
2∞6 卑 2 周 电脑嗲司 第 1'"
霄咆排序的分析与改进
桂尴*
摘 要 从时剧和空间角度全面地矿析立冒泡排序的尾想和持点.在此基础主队记往最后一次文热搅主位置改进立冒 öe，
排序。
关键词 来换排序 冒 öt'，.排序 时间复杂皮
中图:/1'类夸 1 文献标识码 B 文章编号: 1002-2422 ( 2006 )01-∞22-02
The Analysis and Improvement of Bubble Sorting
Abstract The paper analyzes the ídea and feature of bubbling sorting as for the tißÙng and on them by rem-
embering the last exchanging position. the bubbleωrting is improved.
Keyword Exchange Sorting Bubble Sorting Timing Complexity
战们知道交换排序的基本思想川是:两两比较待排序
记录的关键字，发现两个记录的次序相反时即进行交换，直
到世有反序的记录为止。应用变换排序基本思想的主要排
序Hä.二有 3 冒泡排序[1]和快速排序[1) 0 这里我们主要介绍国
泡排序。涉及算法均用 C 语言实现。
1 排序方法
将被排序的记录数组 R [l..nJ 垂直排列，每个记录 R
[iJ石作是重量为 R [í J .key 的气泡。根据轻气泡不能在重
气也之 F的原则，从 F柱上扫描数组 R: 凡扫描到违反本原
则的轻气泡，就使其向上"飘浮飞如此反复进行，直到最后
任何两个气泡都是轻者在上，重者在 F为止回
初始
R [1..nJ 为无序区。
第一次扫描
End U %>
sel se吨sión 飞PageEngine" ) sessÎon (" '在 IE I-:显示水晶报表
从无序区底部向 L依次比较相邻的两个气泡的重量，
若发现轻者在下、重者在1::..则交换二者的位置。即依次比
较 (R [ [n-1]). (R [ [n-2J) ,…, (R
[[IJ); 对于每对气泡 (R [j+IJ , R [j]) ，若 R [j+
J J .key<R [j] .key. 则交换 R [j+l ]和 R [jJ 的内容。
第一次扫描完毕时，"最轻w的气泡就飘浮到该区间的顶
部，即关键字最小的记录被放在最高位置 R [I LI::..
第三次扫描
扫描 R [2..nJ 。扫描完毕时，"次轻w的气泡飘浮到 R
[2] 的位置l: ....•.
最后，经过 n-l 次扫描可得到有序区 R [1..n]
注意z
第 i 次扫描时. R [1..←1]和 R [i..n] 分别为当前的有
序区和无序匾。扫描仍是从无序区底部向上直至该区顶部。
扫描完毕时，该区中最轻气泡飘浮到顶部位置 R [i] 上，结
咛body>
非但IllÙ>
oJ{ptη. PageEngìne
End U
<!一 #include file = "smartvÎewemCIÎvex.
asp"-->
4 结束语
本主介割了参数化水晶报表的 Web 实现原理和」般
程序结构，利用 ASP 和水晶报表开发基于 Web 参数化的报
表向~m程序，结构简单，使用方便，代码重复利用性好，是开
发企业信息系统的一种理想报表手段。
参考文献
[1 ]李云壳，李相枢. .NET 环境 F两种 Web 报表解决H
案的对比分析.成都s 计算机应用研究， 2004 ， 6:212-214.
*桂斌江苏省淮阴师范学院信息传播与技术系助教 Off去 223001 )
22
[2] 张自'bì:. Web 动态报表的实现. 1-:海=计算机应用与
软件.2∞ (4) :110-112.
[3] 冯华英等译.水晶报表 Crys时 Reports 9 从入fJ到精
通.北京:电 f工业出版社.2003.
[4] 精英科技. ASP 核心技术.北京 z 中国电力 H:\ 版社，
2∞1.
[5] 廖信彦. Active se凹er 彻底研究，北京:中
国铁道出版社.20∞.
收稿H 那]， 2005-四-27
d
果是R[1．．i]变为新的有序区。
2排 序 算 法
2．1分析
为每一次排序都使有序 增加，一个气泡，在经过
n一1次排序之后，有序区中就有n一1个气泡，而无序区中气
泡的重量总是大十等于有序区中气泡的重量，所以整个冒
泡排序过程垒多需要进行n一1次排序。
若 某一次排序中未发现气泡位置的交换，则说明待
排序的无序区中所有气泡均满足轻者在上，重者在下的原
则，因此，冒泡排序过程可在此次排序后终止 为此，在下
面给出的算法中，引入一个布尔量exchange，在每次排序开
始前，先将其置为FALSE。若排序过程中发生了交换，则将
其置为 rRUE。各次排序结束时检查exchange，若未曾发生
过交换则终l卜算法， 再进行 F一次排序。
2．2具体算法
void BubbleSort(SeqList R)
( (1．．n)足待排序的文件，采用自下向上扫描，对R做冒泡排序
int i，J；
Boolean exchange； 换标志
for(i=1：i<n：i++)(／屈 多做 n一1次排序
exchange=FALSE： 次排序』r始前，交换标志应为假
for(j=n一1；j)=i；卜一) 当前无序区R[i__兀]自下向上扫描
if(R[j+】]．key<R[j]．key)(破 换记录
R[O]=R[i+1]：／At．[0]仪做暂存单元
R[j+1]=R[jl；
R[j]=R[0]：
exchange=TRUE： 牛了变换，故将交换标志置为真
)
if(!exchange)／／,次排序束发生交换，提前终止算法
return：
}／／endfi,r(外衢环)
／A3ubbleSorl
3算 法 分 析
3．1算法的最好时间复_杂度 门
若文仲的初始状态是 序的，一次扫描即可完成排序。
所需的关键字比较次数c和记录移动次数M均达到最小
值：
Cmin=n一1
Mrain=0。
冒泡排序最好的时间复杂度为O(n)
3．2算法的最坏时间复杂度[门
若初始文件是反序的，需要进行n一1次排序。每次排序
要进行n—i次关键字的比较 (1≤i≤n—l’，且每次比较都
必须移动记录三次来达到变换记录位置。在这种情况下，比
较和l移幼次数均达到最人值：
Cmax=n(n一1)／2：0(I12)
Mmax=3n(I1--1)／2=0(I12)
泡排序的最坏时间复杂度为 O(I12)。
3．3算法的平均时间复杂度为O(I12)
虽然冒泡排序不一定要进行 n一1次，但由于它的记录
移动次数较多，故平均时间性能比直接插入排序要差得多
3．4算法稳定性
冒泡排序是就地排序，且它足稳定的。
4算 法 优 化
4．1记住最后一次交换发生位置lastExchange的冒泡排序
在每次扫描中，记住最后一次交换发生的位置lastEx—
change，(该位置之前的相邻记录均已有序)。 一次排序
开始时，R[1．．1astExchange一1]是有序区，R[1astExchange．．
n]是无序区。这样，一次排序可能使当前有序区扩允多个
记录，从而减少排序的次数。
具体算法；
void BubbleSort(SeqList R)
{／／R(1_．n)是待排序的文什，采用自下向上扫描，对R做冒泡排序
int i，j，k：
Boolean exchange：
for(i--1；i<n：i--k)(
exchange~-FALSE；
for(j=n-1，k=n-1；j)=i；j_一)
if(R Ej+1]．key<R[j]．key){
R[0]=R[j+1]：
R[j+1]=R[j]；
R[j]=R[O]：
k ；
exchange=TRUE；
)
if(!exchange)
return ；
)#endfor(外循环)
}／A3ubbleSort
5 结 束 语
算法的优化是没有止境的，不同的运行环境，不 应用
的需求，对算法的影响也是很显著的。有些算法理论，_}：足优
化了，但实际运行时就不一定最好的。总而言之没有哪一种
算法足最优的，有的适用于N较大的情况，有的适JH于N
较小的情况，有的适用于初始序列基本有序，而有的义在初
始序列基本有序时效率最低，因此不能一概而论，应该具体
情况具体分析。冒泡排序适用于 N较小或初始序列基本有
序的情况。
参 考 文 献
[1]严蔚敏，吴伟民．数据结构 (c语言版)．北京：清华大
学出版社，2000：272—273．
[2]成亚萍．实现冒泡排序算法的一种新方法．淮安：淮阴
师范学院学报(自然科学版)．2003：234—236．
[3]李春葆，李三铁．数据结构考点精要与解题指导．北
京：人民邮电出版社，2002：227-228．
· 23 ·
维普资讯
果是 R [l..i] 变为新的有序区。
2 排序算法
分析
问为每一次排序都便有序I泛增加 J-个气泡，在经过
n-l 次排序之后，有序区中就有 n-l 个气泡，而无序区中气
泡的重量总是大于等 r有序[丘中气泡的重量，所以整个冒
泡排序过程量多需要进行 n-l 次排序。
者在某一次排序中未发现气泡位置的交换，则说明待
排序的;t序[2<:中所有气泡均满足轻者在上，重者在下的原
则，因此，冒泡排序过程可在此次排序后终止。为此，在下
面给山的算拙，中，寻|入一个布尔量 exchange，在每次排序开
始前，先将其置为 FALSEo 若排序过程中发生了交换，则将
其置为 TRUE. 各次排序结束时检查 exchange. 着未曾发生
过交换则终 11::算法，不再进行 F一次排序。
具体算法
void BubbleSort (SeqUsl R)
{j;R (1..旧是待排序的文件，采用自下向上扫描，对 R 做自泡排序
lnt ), j;
B∞lean exchange: 11:变换标志
for< i=l:i<n:i++) { #锺多做 n-l 次排序
exchange=FALSE: #本次排序)f始前，交换标志应为假
for (j=n-l :j>=i:j一〉 β才当前无序区 R [i..nJ 白下向上扫描
if( R [j+l] .key<R [jJ .key) U交换记录
R[O]=R[j+l]: Æ[O] 仪做暂存单元
R [j+ 1] =R [j] ;
R [j ]=R [0];
exch皿ge=TRUE: #发生了交换，故将变换标志置为真
if (!exchange) 元本次排序未发生交换，提前终止算法
return:
}ðendfnr (外循环〉
ÆubbleSort
3 篝 j去分析
算法的最好时间复杂度[1]
若文件的初l)fì状态是 lE序的，一次扫描即可完成排序。
所甫的关键字比较次数 C 和记录移动次数 M 均达到最小
值:
Cmin=n-l
Mmin=O.
国泡排序最好的时间复杂度为 o (n) 0
算法的最坏时间复杂度[1]
:f，'初始丈件是反序的，面要进行 n-} 次排序。每次排序
要进行 n-i 次关键字的比较(1乓i~n-}) .且每次比较都
必须移功记录三次来达到交换记录位置。在这种情况下，比
较和移t;JJ次数均达到最火值2
Cmax=n ( n-l ) ;2:::0 (n2 )
Mma且=3n(n-[)/古=0 (n2 )
国泡扫|序的最坏时间复杂度为 o (n2 ) 。
算法的平均时间复杂度为 o (n2 )
虽然冒泡排序不一定要进行 n-l 次，但由于它的记录
移动次数较多，故平均时间性能比直接插入排序要差得多。
算法稳定性
冒泡排序是就地排序，且它是稳定的。
4 篝法优化
记住最后一改变换发生位置 lastExchange 的冒泡排序
在每次扫描中，记住最后一次交换发生的位置 lastEx
change , (该位置之前的相邻记录均已有序) 0 F一次排序
开始时，R [1..1astExchange-1]是有序区，R [lastExchange..
n] 是无序区。这样，一次排序可能使当前有序区扩充多个
记录，从而减少排序的次数。
具体算法z
void BubbleSort (SeqList R)
{Æ (I..旧是待排序的文件，采用自下向上扫描，对 R 做自泡排序
int ,k;
B咽lean exchange:
for (j"'l:kn ;i",k) {
exchange..FALSE:
for (j=n-l ,k=n-l ;j>=i;j--)
江(R [j+ 1] .key<R [iJ .key) {
R[O] ",R[j+ tJ:
R [j+l] ==R [j] ;
R[j]=R[O] :
k==j;
exchange==TRUE;
}
if(!因change)
retum;
} ðendf.时(外循环〉
} ÆubbleSort
5 结束语
算法的优化是没有止境的，不同的运行环境，不同应用
的需求，对算法的影响也是很显著的。有些算法理论上是优
化了，但实际运行时就不一定最好的。总而言之没有哪←种
算法是最忧的，有的适用于 N 较大的情况，有的适HJ 于 N
较小的情况，有的适用于初始序列基本有序，而有的义在初
始序列基本有序时效率是低，因此不能一概而论，向该具体
情况具体分析。冒泡排序适用于 N 较小或初始序列基本有
序的情况。
参考文献
[1]严蔚敏，吴伟民.数据结构 (C 语吉版上北京:清华大
学出版社， 2∞0:272-273.
[2J 成亚萍实现冒泡排序算法的一种新方法，淮宜 2 淮阴
师范学院学报(自然科学版) .2003: 234-236.
[3] 李春碟，李兰铁.数据结构考点精要与解题指导.北
京:人民邮电出版社， 2002: 227-228.
23
