冒泡排序算法的分析与改进 算法设计

《冒泡排序算法的分析与改进 算法设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析论文冒泡排序算法的分析与改进孙伟（安徽中医学院医药信息工程学院09医软一班，安徽合肥，230009）摘要：冒泡排序算法有两个优点：1“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，但当需要排序的数据较多且无序时，冒泡排序算法的时间复杂度较大，比较次数较多，本文提出了一种冒泡排序算法的改进方法，可以大大减少比较的次数，降低算法的时间复杂度。关键词：交换排序扫描稳定算法中图分类号：TU411.01文献标识码：ABubbleso

2、rtalgorithmanalysisandimprovementSUNWei(AnhuiUniversityofTraditionalChineseMedicineMedicalInformationEngineering,Hefei230009,China；)Abstract:Bubblesortalgorithmhastwoadvantages:1“Programmingcomplexity”isverylow，anditiseasytowritecode;2.Ithasthestabilit

3、y,thestabilityreferstotheoriginalsequenceinthesameelementrelativesequenceremainstosortsequence,butwhentheneedtosortthedataandmoredisordered,bubblesortalgorithmtimecomplexitycomparedtolarger,moreoften,thispaperpresentsabubblesortalgorithmmethod,cangreat

4、lyreducethenumberofcomparisons,reducethetimecomplexityofalgorithm.Keywords：Exchangesort;Scanning;stability;Algorithm———————————————————————————————————————————————————————收稿日期：2012-4-14；作者简介：孙伟1992-10-04女0971303309医软一班算法分析论文算法分析论文1.概述1.1冒泡排序简介冒泡排序法是一种交

5、换排序法，这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不

6、必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。1.2冒泡排序方法冒泡排序法是一种最简单的排序算法,它和气泡从水中往上冒的情况有些类似。其基本算法如下：对1至n个记录，先将第n个和第n-1个记录的键值进行比较，如r[n].key

7、作，则具有次小键值的记录被安置在第2位上。重复以上过程，每次的移动都向最终排序的目标前进，直至没有记录需要交换为止。具体实现时，可以用一支旗子flag表示第i趟是否出现交换。如果第i趟没有交换，则表示此时已完成排序，因而可以终止。1.3冒泡排序过程示例设待排序的键值为：2517651394474194执行冒泡排序的过程如下图所示。其中，第一列为初始键值序列,第二列至第八列依次为各趟排序的结果，图中用方括号括起来的是当前待排序的无序区。每一次排序都使有序区扩充了一个气泡，在经过i次排序之后，有序区中就

8、有i个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，整个冒泡排序过程至多需要进行n-1次排序。但是,若在某一次排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则因此冒泡排序过程可在此次排序后终止。在上图的示例中，在第四次(图中第五列)排序过程中就没有气泡交换位置,此时整个文件已达到有序状态。为此，实际给出的算法中，我们可以引入一个布尔量flag，在每一次排序之前，先将它置为true，若在一次排序中交换了记录,则将它置为