| 冒泡排序算法及其改进算法的实验分析 |
| |
| 引用本文： | 淦艳,杨有,余平.冒泡排序算法及其改进算法的实验分析[J].重庆三峡学院学报,2011,27(3):53-57. |
| |
| 作者姓名： | 淦艳 杨有 余平 |
| |
| 作者单位： | 重庆师范大学计算机与信息科学学院,重庆沙坪坝,400047 |
| |
| 基金项目： | 重庆师范大学博士基金项目(10XLB006); 重庆市教委科技项目(KJ100623)阶段性研究成果 |
| |
| 摘 要： | 排序是计算机科学的基本问题之一.通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算法,总结出它们的时间复杂度为O(n2)和空间复杂度为O(1).通过编程验证了四种排序算法在不同随机度情况下的性能,指出它们的适用原则:当随机度比较小时,应选取非传统冒泡排序算法;当随机度比较大时,则应选取传统冒泡排序算法.实验表明,四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系,传统冒泡排序算法的时间消耗与输入序列随机度近似地呈水平直线关系,而其它三种算法的时间消耗与输入序列随机度呈40?左右的斜线关系.
|
| 关 键 词： | 传统冒泡 带标记 双向冒泡 交替排序 随机度 |
Experiment Analysis on the Bubble Sorting Algorithm and Its Improved Algorithms |
| |
| GAN Yan,YANG You,YU Ping.Experiment Analysis on the Bubble Sorting Algorithm and Its Improved Algorithms[J].JOurnal of Chongqing Three Gorges University,2011,27(3):53-57. |
| |
| Authors: | GAN Yan YANG You YU Ping |
| |
| Institution: | GAN Yan YANG You YU Ping(College of Computer and Information Science,Chongqing Normal University,Chongqing 400047,China) |
| |
| Abstract: | 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-consumi... |
| |
| Keywords: | traditional bubble marked flag two-way bubble alternate sorting degree of random |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
