一种改进的冒泡排序算法研究

　　摘要：在一些数据处理中，排序占有极其重要的位置。一些资料表明，约有近50%以上的CPU处理时间是用于排序数据上的，因此，数据排序就显得尤为重要。本论文阐述了一种改进的冒泡排序法：分析提出这种冒泡排序算法适合应用的数据环境和包含的分支算法。

　　关键词：数据处理；冒泡排序；复杂度；执行效率

　　一、传统冒泡排序实现方法

　　对于某个初始数据，依次比较相邻两个数据，若两个数据大小不符合排序要求时对其交换，直到所有数据有序。

　　例如：对s[8]={49，37，65，97，76，12，27，49}用传统冒泡排序法实现数据排序。

　　初始记录：4937659776122749

　　一次扫描：3749657612274997二次扫描：3749651227497697三次扫描：3749122749657697四次扫描：3712274949657697五次扫描：1227374949657697六次扫描：1227374949657697

　　七次扫描：1227374949657697

　　过程分析与算法的实现。第一次扫描：对初始记录从头至尾依次比较相邻的两个数据大小，若发现大小相反的，小的数据在前、大的数据在后，交换两数据位置。即连续比较（s[0]，s[1]），（s[1]，s[2]），（s[2]，s[3]）…，（s[6]，s[7]）；对于每对相临的两个气泡（s[n-1]，s[n]），若s[n-1]>s[n]，则交换s[n-1]和s[n]的内容。

　　第一次扫描结束后，“最大”的气泡就飘至该序列的最后面，就是最大值被移动至数组最后的位置s[7]上。第七次扫描：经过7趟扫描后即可完成，最终生成有序记录s[0]～s[7]。

　　由于每一次扫描都使有序序列增加了一个“气泡”，在经过n-1次排序扫描后，有序序列中就增加为n-1个气泡，而无序序列中“气泡”的大小总是小于等于有序序列中“气泡”的大小，因此整个冒泡排序的执行过程最多要执行n-1趟排序扫描。

　　二、分析与改进方法

　　通过上面分析可以看出，原始冒泡排序对于n个数据记录来说，整个过程需要执行n-1趟排序，但对于这n-1趟排序过程中，是否有空操作呢？如果某一趟执行过程中没有实现数据的交换，可以说明欲排序的序列中所有数据都满足轻者在前，重者在后的原则，所以，排序执行可在此趟排序后结束，不用再进行无必要的执行。

　　例如排序这样的一个数组序列{13，30，65，65，45，65，65，65}，进行冒泡排序。

　　开始数据序列：1330656545656565

　　第一趟执行后：1330654565656565

　　第二趟执行后：1330456565656565

　　第三趟执行后：1330456565656565

　　第四趟执行后：1330456565656565

　　第五趟执行后：1330456565656565

　　第六趟执行后：1330456565656565

　　第七趟执行后：1330456565656565

　　从实例可以看出，经过两次交换后，记录序列就生成完成，不用再进行排序的执行。因此，可以依据此过程实现一个改进执行的冒泡排序——“标志冒泡排序（ImproveBubble）”。

　　为减少没必要的检查比较，在上述“标志冒泡排序（ImproveBubble）”的基础上还可以加改进，提出“标志冒泡排序（ImproveBubble）”改进后的算法“记住最后一次交换发生位置的冒泡排序（ImproveBubblesort）”。

　　其具体过程为：

　　在每一次扫描过程中，找出并确定最后一次数据执行交换的位置p，可以确认p后面的几个相邻数据均已经有序。下趟排序开始执行前，s[p，…，n-1]就是有序数据范围，w[1，…，p-1]就是无序数据范围。如此执行，每趟排序可以使当前有序数据范围扩充多个数据记录，进而减少排序的次数。

　　例如，一个数组{101，12，18，41，45，44，67，95，98}，对其执行“记住最后一次交换发生位置的冒泡排序（ImproveBubblesort）”。

　　原始记录序列：1011218414544679598第一趟执行后：1218414544679598101

　　第二趟执行后：1218414445679598101第三趟执行后：1218414445679598101

　　可以看出，用“记住最后一次交换发生位置的冒泡排序（ImproveBubblesort）”对这9个数的执行排序后，3次扫描后即可完成，而原始“冒泡排序（Bubblesort）”要执行8次才能实现完成，大大提升了算法的执行效率。

　　综上所述，冒泡排序就是为了得到一个升序或者降序的有序序列。但是达到目的并不是理解排序算法的最终目标，理解排序算法的根本意义是在于有效解决象排序一样的实际问题。参考文献：

　　[1]李春葆等.数据结构设计题典[M].北京：清华大学出版社，2002.368-422

　　[2]（印）克里斯哈拉莫斯（Krishnamoorthy，R.），（印）库玛纳维尔（Kumaravel，G.I.），数据结构[M].北京：清华大学出版社，2009.376-459

　　[3]云微.排序算法的分析与比较实现[J].科技信息，2008.（33）.912-915

　　[4]李宝艳，马英红.排序算法研究[J].电脑知识与技术（学术交流），2007.（08）.1903-1906