APP下载

拆分冒泡排序的算法与实现

2011-03-18王瑜

通化师范学院学报 2011年2期
关键词:排序

王 瑜

(安徽广播电视大学,安徽 合肥230022)

数据结构教材中介绍了几种序列的排序方法,其中快速排序和冒泡排序是两种较长用的排序方法,这两种方法各有特点.对于不同的问题,不同的方法有各自的优势,排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占用量,进而影响整个软件的性能[1].

1 快速排序法和冒泡排序法

1.1 快速排序法

快速排序的基本思想是从要被排序的序列R[1……n]中选定一个记录作为“基准”关键字,从待排序列的两端交替地向中间扫描,将其他记录的关键字k'与k进行比较,若k'k,则将对应记录换到R之后.通过一趟排序将待排序记录分成两部分,排在R之前的记录的关键字均小于等于k,排在R之后的记录的关键字均大于等于k;然后继续对R前后两部分记录进行快速排序,直至排序范围是1为止.

1.2 冒泡排序法

冒泡排序的基本思想是:将相邻的两个数据元素按关键字进行比较,如果反序则交换.对于一个待排序的数据元素序列,经一趟排序后最大值数据元素移到最大位置,其它值较大的数据元素也向最终位置移动,此过程为一次起泡.然后对下面的记录重复上述过程直到过程中没有交换为止,则已完成对记录的排序[2].

1.3 两种排序方法的比较

快速排序和冒泡排序的时间效率都与初始序列有关,对于快速排序而言,初始序列为向有序时的时间复杂度为O(n2),无序情况下的时间复杂度为O(nlg2n);而对于冒泡排序来说

登录APP查看全文

猜你喜欢

排序
排排序
作者简介
作者简介
作者简介(按文章先后排序)
恐怖排序
律句填空排序题的备考策略
节日排序
刻舟求剑
作者简介(按文章先后排序)
2010年