拆分冒泡排序的算法与实现
2011-03-18王瑜
通化师范学院学报 2011年2期
关键词:排序
王 瑜
(安徽广播电视大学,安徽 合肥230022)
数据结构教材中介绍了几种序列的排序方法,其中快速排序和冒泡排序是两种较长用的排序方法,这两种方法各有特点.对于不同的问题,不同的方法有各自的优势,排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占用量,进而影响整个软件的性能[1].
1 快速排序法和冒泡排序法
1.1 快速排序法
快速排序的基本思想是从要被排序的序列R[1……n]中选定一个记录作为“基准”关键字,从待排序列的两端交替地向中间扫描,将其他记录的关键字k'与k进行比较,若k'
1.2 冒泡排序法
冒泡排序的基本思想是:将相邻的两个数据元素按关键字进行比较,如果反序则交换.对于一个待排序的数据元素序列,经一趟排序后最大值数据元素移到最大位置,其它值较大的数据元素也向最终位置移动,此过程为一次起泡.然后对下面的记录重复上述过程直到过程中没有交换为止,则已完成对记录的排序[2].
1.3 两种排序方法的比较
快速排序和冒泡排序的时间效率都与初始序列有关,对于快速排序而言,初始序列为向有序时的时间复杂度为O(n2),无序情况下的时间复杂度为O(nlg2n);而对于冒泡排序来说
登录APP查看全文
