一种基于冒泡排序算法的改进.pdf

《一种基于冒泡排序算法的改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第19卷第3期梧州学院学报No.3Vol.192009年6月JOURNALOFWUZHOUUNIVERSITYJun.2009一种基于冒泡排序算法的改进梁文忠（梧州学院数理系，广西梧州543002）[摘要]该文提出了基于冒泡排序算法的改进，通过在每趟循环中确定不止一个元素经排序后的位置，减少排序过程中循环所需的趟数，提高将数据元素从无序序列到有序序列的实现速度。[关键词]算法；冒泡排序；改进[中图分类号]TP301.6[文献标识码]A[文章编号]1673-8535(2009)03-0061-05AnImprovedAssumptionBasedonBu

2、bbleSortLiangWenzhong(TheDepartmentofMath&Phys,WuzhouUniversity,Wuzhou543002,China)Abstract:Thisarticlemakesanimprovementbasedonbubblesortwhichisfrom"AnImprovedAssumptionBasedonStraightSelectionSorting".Itdemonstratesthattheassumptioncanspeeduptheorderingofdatafromdisordertoorde

3、rthroughlocatingthepositionofmorethanoneelementsafterorderingineachcirculationandreducingthecirculationsneededinordering,.Keywords:arithmetic;BubbleSort;improvement排序作为数据处理中的一种重要运算，其本质就是将一组数据元素的无序序列按一定规律排列，使[1-2]其成为有序序列。在当今的计算机系统中，花费在数据排序的时间占系统整个运行时间的比重是很可观的，通过研究和改进排序算法来提高计算机处理系

4、统的工作效率是非常有价值的。笔者改进了参考文献[3]的方法，提出了通过在每趟循环中确定不止一个元素经排序后的个数，减少排序过程中循环所需的趟数，可以提高将数据元素从无序序列到有序序列的实现速度。实际上，以这样的策略也可以实现对冒泡排序算法的改进。为了方便讨论，笔者假设待排序的一组记录存放在一组地址连续的存储单元中，并设记录关键字为整数，因而待排序记录的数据类型为：typedefstruct/*记录为一结构类型*/{intkey;/*关键字域*/elemtpotheritem;/*记录的其他字域*/}recdtype;reedtypeR[];/*R为一记

5、录类型数组*/收稿日期：2009-02-16基金项目：梧州学院科研项目（2007B007）·61·梁文忠：一种基于冒泡排序算法的改进1冒泡排序冒泡排序是内排序中一种重要的排序策略。冒泡排序的基本原理是通过相邻记录之间的比较和交换使关键字值较小的记录逐渐从底部向顶部，即从下标较大的单元向下标较小的单元移动，就像水底的气泡一样向上冒。冒泡排序的具体做法可描述为：先将初始文件的第n个记录的关键字值和第n-1个记录的关键字值进行比较，若发现次序相反（即逆序，R[n-1].key>R[n].key），则交换两个记录；然后比较第n-1个记录和第n-2个记录的关键字

6、值，若为逆序，又交换两个记录；如此下去，直到第2个记录和第1个记录的关键字值进行比较为止，这样就完成了第1趟排序。经过第1趟排序后，关键字值最小的记录被放置到R[0]的位置上；然后再进行第2趟排序，对剩下的n-1个记录再进行类似的操作，其结果是关键字值较小的记录被安置到R[1]位置上，重复进行n-1趟后，整个冒泡排序结束。例如，对一组具有8个记录的数据进行冒泡排序，其关键字值分别为（46，26，43，18，74，21，43`，53），表1给出了冒泡排序的过程。表1冒泡排序示例表第1趟第2趟第3趟第4趟第5趟第6趟第7趟初始状态排序后排序后排序后排序后排

7、序后排序后排序后R[0].key4618181818181818R[1].key2646212121212121R[2].key4326462626262626R[3].key1843264643434343R[4].key742143434643`43`43`R[5].key217443`43`43`464646R[6].key43`43`745353535353R[7].key5353537474747474从上述冒泡排序示例中可以看出：对任一组记录进行冒泡排序时，至多要进行n-1趟冒泡排序。若达到某一趟排序末没有记录位置的交换，则说明待排序记录已

8、按关键字值有序，整个文件已达到有序状态，此时冒泡排序可在此趟排序后终止。2改进设想依据参考文献