《双向起泡的排序算法》由会员分享，可在线阅读，更多相关《双向起泡的排序算法（10页珍藏版）》请在金锄头文库上搜索。
1、. . 双向起泡的排序算法1.课题容和要求1.1课题容：双向起泡的排序算法，即相邻两遍向相反的方向起泡。双向起泡排序法，向两个方向漂浮，通过一趟排序，可找出关键字“最大”和“最小”的两个记录，因而相比起泡算法速度大大提高了1.2要求1） 设计一个排序算法，使之拥有通过一次循环使两端得到最大数最小数的功能2） 与起泡法相比较，在时间性能上要有一个很大的突破1. 设计思路分析2.1基本思想起泡排序的基本思想起泡排序易于冒泡排序算法合并，即向后推出最大数。将被排序的记录数组R1.n垂直排列，每个记录Ri看作是重量为Ri的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的
2、轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。一般地，第i遍处理时，不必检查第i个位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。即就是在一组待排序的数据中，两两比较数据的大小，发现两个记录的排序次序相反时就交换位置，直到没有反序的记录为止。也就是说它重复地走访过要排序的序列，一次比较两个项目，如果他们的顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有再需要做交换动作，该序列已经排序完成。一趟冒泡，至少可以把值最大的元素送到最后位置(或最上边)；当然也可以倒过来做，把值小的元素向前移或向下移，一趟冒泡，至少可以把值最小的元
3、素送到最前面的位置(或最下边)。双向起泡排序算法思想 双向起泡排序是冒泡排序的升级版，双向起泡排序连够在一次循环中同时取得最大值与最小值，所以用双向冒泡排序的交换的次数减少了，从而达到了优化起泡法的作用。双向起泡法和通常的冒泡法比较，两者比较次数基本相同，但数据交换的次数相差很大，双向起泡法要大大小于冒泡法。2.2算法分析：1，分析双向起泡排序与传统的起泡排序非常相似，只不过起泡排序对数据序列的扫描始终朝着一个方向，而双向起泡排序对数据序列的扫描是在两个方向上交替进行双向起泡排序算法设计难度略高于起泡排序，但它使排序效率在一定围有一定程度的提高上述双向起泡排序算法至少需进行1趟扫描，至多需进行
4、n一1趟扫描，即在待排序数据初始有序(正序)情况下，关键字的比较次数为”一1，数据的移动次数为0；在待排序数据初始逆序的情况下，关键字的比较次数为”(z一1)2，最坏情况下，每一次比较均会发生数据的交换，即移动次数为3n(1)2显然双向起泡排序与起泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同2.性能测试比较由于渐进复杂度分析的方法不能区分具有相同时间复杂度的算法，因此需要进行进一步测试有研究设计者对双向起泡排序和起泡排序算法进行270延边大学学报(自然科学版)第27卷了性能对比测试，结果如表1所示测试所用数据均为16位非负随机数测试结果表明
5、，双向起泡排序与起泡排序算法的平均移动次数始终相同；而对随机给出的数据序列，双向起泡排序算法要比起泡排序算法的平均比较次数要少由于测试程序的统计量不是运行时间，所以测试结果不依赖于具体计算机的软、硬件等环境因素，而仅与算法有关虽然在不同的计算机硬件、软件环境下，对于不同的待排序数据序列，其运行时间的测试结果也会不同，但表中数据可以在一定程度上反映算法的性能测试结果表明，当数据量不大时，双向起泡排序并不比起泡排序效率更高，这是由于双向起泡排序算法平均比较次数较少的优点不足以抵消其程序结构复杂所带来的额外开销，而当数据量较大时，双向起泡排序的时间性能则明显优于起泡排序运行时间的测试结果。2.3事例
6、比较： 初始关键字： 49 38 65 97 76 13 27 46 冒泡排序： 49 38 65 97 76 13 27 46第一趟结果：38 49 65 76 13 27 46 (97)第二趟结果：38 49 65 13 27 46 (76)第三趟结果：38 49 13 27 46 (65)第四趟结果：38 13 27 46 (49)第五趟结果：13 27 38 (46)第六趟结果：13 27 (38)第七趟结果：(13) (27)从图中可以看出, 每一趟排序, 关键字“ 最大” 的记录漂浮到了水面上, 关键字较小的记录在逐渐下沉, 每一趟排序有一个关键字“ 最大” 的记录漂浮到了水面4。
7、那么能不能在一趟排序中, 让关键字“最小” 的也同时沉到水底呢？ 这就是以下我们要介绍的双向起泡排序法。 双向起泡排序法的基本思想是, 通过一趟排序, 找出关键字“ 最大” 和“ 最小” 的两个记录, 关键字大的向上浮到水面, 关键字小的向下沉到水底, 再进行第二趟排序, 找出关键字次大和次小的记录。双向起泡排序 49 38 65 97 76 13 27 46 R1 R8 第一趟结果： 13 46 49 65 76 38 27 97R2 R7第二趟结果： 27 46 49 65 38 76R3 R6第三趟结果： 38 46 49 65R4 R5第四趟结果： 46 49双向起泡法和通常的冒抱法相
8、比较, 两者数据比较的次数基本相同, 但数据交换的次数相差很大, 双向起泡法要大大小于冒泡法。 如对于10个记录的序列, 若初始序列为“ 逆序” , 用冒泡法进行排序时, 第一趟排序, 需进行9次比较, 相应的也需9 次交换, 才能找到关键字最大的记录；采用双向起泡排序法, 进行一趟排序, 需进行9次比较, 1次交换, 找到了关键字最大和最小的两个记录。 采用冒泡法需进行9趟排序, 而采用双向起泡法只需5 趟就可以达到目的。因而从性能上讲, 双向起泡排序法大大优于通常的冒泡法, 特别是对于大量的数据, 就更显其优越性。 3.概要设计 3.1双向起跑排序流程图：1) 逆向起泡排序：jiYYN变量
9、赋初值：m=0Count+j-flag=1m=rjrj=rj-1rj-1=mj-rj-1rj？/i=nN变量赋初值：i=0，j=n-1开始i=i+1N输出排好序的数组rj结束2）正向起泡排序：jrj+1？/i=nN变量赋初值：i=0，j=n-1开始i=i+1N输出排好序的数组rj结束 3.2类中成员变量和成员函数原型声明Sort(int r,int m,int n); /构造函数，建立排序数组，采用顺序存储结构实现void BiBubble(int r,int n); /双向起泡排序算法void print(int n,int r); /输出排好序的数组 4.详细设计 4.1源程序设计1） 构
10、造函数Sort:Sort(int r,int m,int n) /函数的传值调用显得尤为重要，这是函数的入口,注意形参中的参数必须和程序中的参数是一致的，不然的话就会出现未定义cout实际输入的元素个数为n个endl;r0=0;for(int i=1;in+1;i+) /由于第一个数组元素置空，那么就会有一个元素无法进入数组导致，输入元素比实际的少一个，因此循环加1 cout请输入你要是排序的第iri; mi=ri; cout您输入的元素如下：;for(i=1;in+1;i+) coutri ;couti;j-) /逆向起泡排序,这里的j为n-i从最后一个元素开始比较 if(rj-1rj) f
11、lag=1; int m; m=rj; rj=rj-1; rj-1=m; count+; /发生了交换，故将交换标志置为真 for(j=i+1;jrj+1) flag=1; int s; s=rj; rj=rj+1; rj+1=s; count+; i+;cout比较的次数是：countendl;3） 输出排好序的数组void Sort:print(int n,int r)for(int i=1;in+1;i+) coutri ;4） mian函数void main()int bMaxSize; /辅助初始数组int aMaxSize; /待排序数组int n; /全局变量以便调用coutn;Sort s(a,b,n); s.BiBubble(a,n); s.print(n,a);coutendl;5.测试数据及其结果分析5.1系统功能测试的数据和测试结果测试一：测试二：5.2结果分析1） 测试一：4 7 0 3 6
