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

算法分析论文冒泡排序算法的分析与改进孙伟（安徽中医学院 医药信息工程学院 09医软一班，安徽合肥，230009）摘 要： 冒泡排序算法有两个优点：1“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，但当需要排序的数据较多且无序时，冒泡排序算法的时间复杂度较大，比较次数较多，本文提出了一种冒泡排序算法的改进方法，可以大大减少比较的次数，降低算法的时间复杂度。关键词：交换排序 扫描 稳定 算法中图分类号：TU 411.01 文献标识码：A Bubble sort algorithm analysis and improvementSUN Wei(Anhui University of Traditional Chinese Medicine Medical Information Engineering, Hefei 230009, China；)Abstract: Bubble sort algorithm has two advantages:1 “Programming complexity”is very low，and it is easy to write code;2.It has the stability, the stability refers to the original sequence in the same element relative sequence remains to sort sequence, but when the need to sort the data and more disordered, bubble sort algorithm time complexity compared to larger, more often, this paper presents a bubble sort algorithm method, can greatly reduce the number of comparisons, reduce the time complexity of algorithm.Key words：Exchange sort ; Scanning ; stability ; Algorithm收稿日期：2012-4-14；作者简介：孙伟 1992-10-04 女 09713033 09医软一班 算法分析论文 1.概述1.1 冒泡排序简介冒泡排序法是一种交换排序法，这种方法的基本思想是，将待排序的元素看作是竖着排列的“ 气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“ 气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“ 轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“ 最轻”的元素就浮到了最高位置；处理二遍之后，“ 次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“ 最轻”元素，所以不必检查。一般地，第i 遍处理时，不必检查第i 高位置以上的元素，因为经过前面i- 1遍的处理，它们已正确地排好序。1.2 冒泡排序方法冒泡排序法是一种最简单的排序算法,它和气泡从水中往上冒的情况有些类似。其基本算法如下：对1 至n 个记录，先将第n 个和第n- 1 个记录的键值进行比较，如rn.keyrn- 1.key,则将两个记录交换。然后比较第n- 1 个和第n- 2 个记录的关键字； 依次类推， 直到第2 个记录和第1 个记录进行比较交换，这称为一趟冒泡。这一趟是所实现的功能：将键值最小的记录传到了第1 位。然后，再对2 至n 个记录进行同样操作，则具有次小键值的记录被安置在第2 位上。重复以上过程， 每次的移动都向最终排序的目标前进，直至没有记录需要交换为止。具体实现时，可以用一支旗子flag 表示第i 趟是否出现交换。如果第i 趟没有交换，则表示此时已完成排序，因而可以终止。1.3 冒泡排序过程示例设待排序的键值为：25 17 65 13 94 47 41 94执行冒泡排序的过程如下图所示。其中，第一列为初始键值序列,第二列至第八列依次为各趟排序的结果， 图中用方括号括起来的是当前待排序的无序区。每一次排序都使有序区扩充了一个气泡，在经过i 次排序之后，有序区中就有i 个气泡， 而无序区中气泡的重量总是大于等于有序区中气泡的重量，整个冒泡排序过程至多需要进行n- 1 次排序。但是,若在某一次排序中未发现气泡位置的交换， 则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则因此冒泡排序过程可在此次排序后终止。在上图的示例中，在第四次(图中第五列)排序过程中就没有气泡交换位置,此时整个文件已达到有序状态。为此，实际给出的算法中， 我们可以引入一个布尔量flag， 在每一次排序之前， 先将它置为true，若在一次排序中交换了记录,则将它置为false。当一次排序结束时，我们再检查flag，若未曾交换过记录便终止算法。该算法的时间复杂性为0(n2),算法为稳定的排序方法。2.对于冒泡算法的改进2.1 第一种改进方法如果在某一趟循环中没有任何数据交换发生， 则表明数据已经排序完毕。那么剩余的循环就不需要再执行假设需要排序的数据已经按照从小到大排列，那么第一趟比较就不会有任何数据交换发生。这种改进算法如下：设置一个标志位，当没有交换的时候这个标志位不会变化，那么说明数据已经排序好了，就不需要再进行剩余的循环。只有在标志位被重新设置的情况下才会进行剩余的循环。publicstaticvoid ImproveBubble1(int myArray)bool isSorted = false;for(int i = 0; i myArray.Length - 1 &!isSorted; i+)/ 只有在没有排序的情况下才继续循环 isSorted =true; / 设定排序标志for(int j = 0; j myArrayj+1 ) isSorted =false; / 如果是没有排序，就重新设定标志Swap(refmyArray, refmyArrayi+1);从这种算法可以看出，若记录的初始状态是正序（ 从小到大） 的，则一趟扫描即可完成排序。所需的较和记录移动的次数分别达到最小值n- 1 和0。即算法最好的时间复杂度为0(n)；若初始记录是反序（ 从大到小） 的，则需要进行n- 1 趟排序，每趟排序要进行n- i 次关键字的比较，且每次比较都必须移记录三次来达到交换记录位置。在这情况下比较和移动次数达到最大值：比较次数：Cmax= n(n- 1)/2 移动次数： Mmax=3n(n- 1)/2因此这种改进方法的最坏时间复杂度也为0(n2)。在平均情况下，算法可能在中间的某一趟排序完后就终止，但总的比较次数仍为0(n2)，所以算法的平均时间复杂度为0(n2)。因此，这种算法最好的时间复杂度为0(n)。平均，最坏时刻复杂度为0(n2)。2.2 第二种改进方法在冒泡排序的每趟扫描中， 记住最后一次交换发生的位置lastexchange也能有所帮助。因为该位置之前的相邻记录已经有序，故下一趟排序开始的时候，0 到lastexchange 已经是有序的了，lastexchange 到n- 1是无序区。所以一趟排序可能使当前有序区扩充多个记录。即较大缩小无序区范围，而非递减1，以此减少排序趟数。这种算法如下：在冒泡排序中，每趟排序实现了将最大(升序)或最小(降序)的记录安置到未排序部分的最后位置，即最终位置。通过进一步观察研究，由于每趟排序过程中，通过和邻记录关键字两两比较，大(升序)或小(降序)的记录在不断地往下沉或往后靠，小(升序)或大(降序)的记录在不断往上冒或往前靠。每经过一趟排序，在最后次交换位置后面的记录都已经排好序。根据上面的思路，对n 个记录进行第k 趟排序，首先需在第k- 1 趟排序时记下最后交换的位置。然后在第k 趟排序时，将第一个记录的关键字与第二个记录的关键字进行比较，符合交换条件时，进行交换。再比较第二个记录和第三个记录的关键字，依次类推，直至第m- 1 个记录和第m 个记录的关键字进行比较，而不需要比较至n- k- 1 个记录。在大部分排序中，m 都小于n- k- 1从而减少了比较趟数和每趟的比较次数。由于在第一趟排序时，没有上一趟排序的m 值。因此，还要设置m 的初始值为n- 1。publicstaticvoid ImproveBubble2(int myArray) int m= myArray.Length -1;int k, j;while(m 0 ) for( k=j=0; jmyArrayj+1)Swap(refmyArrayj, refmyArrayj+1);k = j; / 记录每次交换的位置m= k; / 记录最后一个交换的位置从这种算法可以看出，若记录的初始状态是正序（ 从小到大） 的。则一趟扫描即可完成排序， 所的关键比较和记录移动的次数分别达到最小值n- 1 和0。即算法最好的时间复杂度为0(n);若初始记录是反序（ 从大到小） 的，则需要进行n- 1 趟排序，每趟排序要进行n- i 次关键字的比较，且每次比较都须移动记录三次来达到交换记录位置。在这情况下比较和移动次数达到最大值：比较次数：Cmax= n(n- 1)/2 移动次数Mmax=3n(n- 1)/2因此，这种办法的最坏时间复杂度也为0(n2)。在平均情况下，算法较大地改变了无序区的范围，从而减少了比较的次数，但总的比较次数仍为0(n2)。所以算法的平均时间复杂度为0(n2)。因此，算法2 最好的时间复杂度为0(n)。平均，最坏时刻复杂度为0(n2)。2.3 双向扫描冒泡法若记录的初始状态为:只有最轻的气泡位于dn的位置(或者最重的气泡位于d0位置)，其余的气泡均已排好序。在上述三种算法中都要做n- 1 趟扫描。实际上只需一趟扫描就可以完成排序。所以对于这种不对称的情况。可对冒泡排序又作一次改进。在排序过程中交替改变扫描方向。即先从下扫到上，再从上扫到下，来回地进行扫描，这样就得到双向冒泡排序算法。对n 个记录进行排序时，设up 记录了从前面向后面依次进行扫描时最后的交换位置，low记录了从后面向前面依次进行扫描时最前的交换位置。由上个改进的冒泡排序的原理可知，up 后面的记录和low 前面的记录都已有序。每趟排序都由两次不同方向的比较、交换组成。第一次是从未排好序的第一个记录开始，即从low 记录开始，向后依次两两比较，如果不符合条件，则交换之，直至比较到未排好序的最后一个记录，即up 记录为止。同时记下最后一次交换的位置，并存于up。第二次是从未排好序的最后一个记录开始,即从up 记录开始，向前依次两两比较，如果不符合条件，则交换之，直至比较到未排好序的第一个记录，即low记录为止。同时记下最后次交换的位置，并存于low。这样，就完成了一趟排序。每趟排序都实现了将未排好序部分的关键字大的记录往后移(升序)，关键字小的记录往前移（ 升序)，从而使两端已排好序（ 如果是降序，记录移动的方向则相反)。未排好序部分的记录的首尾位置分别由low和up 指明。不断按上面的方法进行排序，使两端已排好序的记录不断增多，未排好序部分的记录逐渐减少。即low 和up 的值不断接近，当low=up 时，表明已没有未排好序的记录，排序就完成了。由于在第一趟排序时，没有上趟排序的low和up 值。因此，还要设置low 和up 的初始值分别为0 和n- 1。publicstaticvoid ImproveBubble3(int myArray) int low, up, index, i;low= 0;up = myArray.Length - 1;index = low;while( up low) for( i=low; imyArrayi+1)Swap(refmyArray, refmyArrayi+1);index = i;up= index; / 记录最后一个交换的位置for(i=up; ilow; i- - ) / 从最后一个交换位置处从下向上扫描 if(myArraymyArrayi- 1)Swap(refmyArray, refmyArrayi- 1);index = i; low= index; / 记录最后一个交换的位置从这种算法可以看出，若记录的初始状态是正序（ 从小到大） 的，则一趟扫描即可完成排序。所需的关键比较和记录移动的次数分别达到最小值n- 1 和0。即算法最好的时间复杂度为0(n);若初始记录是反序（ 从大到小） 的，则需要进行n/2趟排序。如果只有最重的气泡在最上面（ 或者最轻的气泡在最下面） ，其余的有序，这时候就只需要比较1 趟。但是在最坏的情况下，算法的复杂度也为0(n2)。因此，算法最好的时间复杂度为0(n)，最坏时刻复杂度为0(n2)。3.性能分析为了分析数据两种冒泡排序法的性能， 我们用自编的测试程序对大量数据进行了测试，得出下表，从表中可以直观地看出两种冒泡排序方法的性能差异（ 时间单位为毫秒）。图1 算法运行时间比较表4.结束语从上面的表格可以看出，在数据量比较小的时候，这几种算法基本没有任何区别。当数据量比较大的时候，双向扫描冒泡排序会有更好的效率。但是效率并没有根本的提升。因此冒泡排序确实不是我们排序的首选。在数据量比较大的时候，快速排序等会有非常明显的优势。