论文部分内容阅读
排序是计算机科学的基本问题之一。通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算法，总结出它们的时间复杂度为O（n^2）和空间复杂度为O（1）。通过编程验证了四种排序算法在不同随机度情况下的性能，指出它们的适用原则：当随机度比较小时，应选取非传统冒泡排序算法；当随机比较大时，则应选取传统冒泡排序算法。实验表明，四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系，传统冒泡排序算法的时间消耗与输入序列随机度近似地呈水平直线关系，而其他三种算法的时间消耗与输入序列随机度呈40°左右的斜线关