长沙市中考满分作文-冒泡排序法及其改进

《长沙市中考满分作文-冒泡排序法及其改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第2O卷第3期青海大学学报(自然科学版)V01．20No．32002年6月JournalofQinghaiUniversityJun．20o2冒泡排序法及其改进郑国彪，曹侃宇2(1．青海民族学院，青海西宁810007；2．西宁市教委。青海西宁810000)摘要：冒泡排序作为一种较为先进的排序方法，在程序开发中广为应用，文中对该方法进行了改进，给出更为先进的冒泡排序法。关键词：冒泡排序法；改进中图分类号：TP311文献标识码：B文章编号：1006—8996(2002)o3—0043—041冒泡排序的基本思想及其

2、实现1．1冒泡排序的基本思想首先将无序表中的第一个记录的关键字(用r[1]．key表示)和第二个记录的关键字(用r[2]．key表示)进行比较，若r[1]．key>r[2]．key，则将这两个记录的内容进行交换，否则不交换。然后比较第二个和第三个记录的关键字，依此类推，直到第n一1条记录和第n条记录进行比较，交换后为止。经过这样一趟排序，即把表中最大的关键字查找出来并放于最后一个记录的位置上⋯。其次，再对前n一1个记录进行同样的比较、交换，操作结束后则把具有次大的关键字的记录放到第一1个记录的位置上。重复以上过程直到无记录交换为止。完成上述全部操作后，便可

3、得到一个数据由小到大排序的有序表。下面以有7个记录的无序表为例，给出冒泡排序的过程图(在所给的无序表中，每一记录只有一个数据项，即所有记录的关键字即是记录内容本身)。表的初始状态：[49386597761327]第一趟排序之后：[384965761327]97第二趟排序之后：[3849651327]7697第三趟排序之后：[38491327]657697第四趟排序之后：[381327]49657697第五趟排序之后：[1327]3849657697第六趟排序之后：132738496576971．2冒泡排序法的实现有了上述基本思想便不难写出其实现程序，下面以

4、汇编语言给出冒泡排序的实现程序。STACKSEGMENTPARASlTACK’SrACK’DB128DUP(0)STACKENDSD['ASEGMENTARRAYDW49，38，65，97，76，13，27WORD．COUNTDW$一ARRAY／2，数据个数(以字为单位)DATAENDSCODESEGMENTASSUMECS：CODE，DS：DI’A，ES：DATA收稿日期；2002—03—14作者简介：郑国彪(1967一)，男，青海湟源人，讲师。维普资讯http://www.cqvip.com青海大学学报第2o卷bubble．sortPROCFARPUS

5、HDSXORAX．AXPUSHAXMOVAX．DATAMOVDS，AXMOVES．AxR姗Y：CMPXCHG．FLAG．0JEEⅪn’DECWORD．COUN，rMOVCX，WORD．COUNT；本趟比较次数一MOVSI，OFFSETARRAY；数据首地址一SICLD【DDSW；取一个数据库一AxCMPAX，[SIj；与下一个数据进行比较JI_ENE)(rI'2；前一数据小转NEXT2XCHG[SI]，AXXCHGlSI一2，AX]；后一数据小，进行交换NE)(rI'2：LooP陋XT1；循环进行两两数据的比较JMPSHORTRⅢRY；转RE3~Y，继续进

6、行下一趟排序EXrr：RET；排序完成，返回DOSbubble-sortNEDPCODEENDsENDbubble．sort2冒泡排序法存在的不足及改进方法首先，在上述排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否已完成排序，为了解决这一不足，可设置一个标志单元xCHGF1AG，将其初值置为OFFH，表示被排序的表是一个无序的表。在每一排序开始时，首先检测此标志，若此标志为0，则结束排序；若此标志为OFFH，则准备进行排序，并预置此标志为0，然后进行本次排序比较，若在本次两两比较后，发生了交换，则重新置标志为OFFH，以便在下一

7、次排序时检测此标志，继续进行排序。若两两比较后，本次未发生交换，则置标志为0，表示数据已排好序，从而使下一次排序不再进行。冒泡排序法的另一不足是当被排序的数据项比较多时，排序的时间会明显延长。下面给出一种改进的方法，以实现快速排序。通过一趟排序将所有记录分成两部分，然后分别对这两部分进行冒泡排序，最终达到全部排序的目的。具体做法：任意选取某一记录(通常取第一个记录)，比较其关键字与所有记录的关键字，并将关键字比它小的记录全部存放于它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在位置为分界点，分为两部分。在进一步比较

8、时，可设两个指针i和i(程序设计中用SI作为i指针，用DI作为i指