冒泡排序算法及其改进算法的实验分析.pdfVIP

重庆航天职业技术学院学报GeneralNo.7

总第7期

2010年9月JournalofChongqingAerospacePolytechnicSep.2010

冒泡排序算法及其改进算法的实验分析

尚晋淦艳2

(1.重庆航天职业技术学院，重庆江北区400021;

2.重庆师范大学计算机与信息、科学学院，重庆沙坪坝400047)

摘要:排序是计算机科学的基本问题之一。通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算

2

法，总结出它们的时间复杂度为0(n)和空间复杂度为00)。通过编程验证了四种排序算法在不同随机度情况下

的性能，指出它们的适用原则:当随机度比较小时，应选取非传统冒泡排序算法;当随机比较大时，则应选取传统冒

泡排序算法。实验表明，四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系，传统冒泡排序算法的时间

消耗与输入序列随机度近似地呈水平直线关系，而其他三种算法的时间消耗与输入序列随机度呈40。左右的斜线

关系o

关键词:传统冒泡带标记双向冒泡交替排序随机度

ExperimentAnalysisontheBubbleSortingAlgorithmand

ImprovedAlgorithms

ShαngJin1,GαnYIαn2

(1.ChongqingAerospacePolytechnic,JiangbeiDistrict,Chongqing400021;

2.CollegeofComputerandInformationScience,ChongqingNormalUniversity,

Shapingba,Chongqing400047)

Abstract:Sortingisthebasicproblemofcomputerscience.Aftertheintroductionoffourbubblesorting

algorithm:traditional,markedflag,two-waybubbleandalternate,thetimeandspacecomplexityofthese

2

algorithmsweresummarized.TheyareallO(n)andO(1).Theperformancesofthesealgorithmswere

verifiedbyprogramming.Theresultwasthatnon-traditionalsortingalgorithmsweretimecost-lessthan

traditionalwhentherandomdegreeofinputsequencewaslow,otherwisethetraditionalwastimecost-

less.Theexperiment