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

Experiment Analysis on the Bubble Sorting Algorithm and Its Improved Algorithms

作　　者：淦艳[1] 杨有[1] 余平[1] 

机构地区：[1]重庆师范大学计算机与信息科学学院

出　　处：《重庆三峡学院学报》2011年第3期53-57,共5页Journal of Chongqing Three Gorges University

基　　金：重庆师范大学博士基金项目(10XLB006);重庆市教委科技项目(KJ100623)阶段性研究成果

摘　　要：排序是计算机科学的基本问题之一.通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算法,总结出它们的时间复杂度为O(n2)和空间复杂度为O(1).通过编程验证了四种排序算法在不同随机度情况下的性能,指出它们的适用原则:当随机度比较小时,应选取非传统冒泡排序算法;当随机度比较大时,则应选取传统冒泡排序算法.实验表明,四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系,传统冒泡排序算法的时间消耗与输入序列随机度近似地呈水平直线关系,而其它三种算法的时间消耗与输入序列随机度呈40?左右的斜线关系.Sorting is the basic problem of computer science.After the introduction of four bubble sorting algorithm： traditional,marked flag,two-way bubble and alternate,the time and space complexity of these algorithms are summarized.They are all O（n2） and O（1）.The performances of these algorithms are verified by programming.The result is that non-traditional sorting algorithms are less time-consuming than traditional ones when the random degree of input sequence is low;otherwise the traditional was less time-consuming.The experiment reveals three approximate relationships.One is four algorithms＇ time cost and input scale could be characterized by an exponential curve.The second is the traditional algorithm＇s time cost and random degree could be described by a horizontal line.The last is the non-traditional algorithms＇ time cost and random degree could be depicted by a line with the slope of 40？.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]