双向起泡的排序算法

1、双向起泡的排序算法1课.题内容和要求课1题内容：双向起泡的排序算法，即相邻两遍向相反的方向起泡。双向起泡排序法，向两个方向漂浮，通过一趟排序，可找出关键字“最大”和“最小”的两个记录，因而相比起泡算法速度大大提高了1.要2求1）设计一个排序算法，使之拥有通过一次循环使两端得到最大数最小数的功能2）与起泡法相比较，在时间性能上要有一个很大的突破1.设计思路分析基1本思想起泡排序的基本思想起泡排序易于冒泡排序算法合并，即向后推出最大数。将被排序的记录数组垂直排列，每个记录看作是重量为的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复

2、进行，直到最后任何两个气泡都是轻者在上，重者在下为止。一般地，第的遍处理时，不必检查第的个位置以上的元素，因为经过前面的-遍1的处理，它们已正确地排好序。即就是在一组待排序的数据中，两两比较数据的大小，发现两个记录的排序次序相反时就交换位置，直到没有反序的记录为止。也就是说它重复地走访过要排序的序列，一次比较两个项目，如果他们的顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有再需要做交换动作，该序列已经排序完成。一趟冒泡，至少可以把值最大的元素送到最后位置（或最上边）；当然也可以倒过来做，把值小的元素向前移或向下移，一趟冒泡，至少可以把值最小的元素送到最前面的位置或最下边）双向起泡

3、排序算法思想双向起泡排序是冒泡排序的升级版，双向起泡排序连够在一次循环中同时取得最大值与最小值，所以用双向冒泡排序的交换的次数减少了，从而达到了优化起泡法的作用。双向起泡法和通常的冒泡法比较，两者比较次数基本相同，但数据交换的次数相差很大双向起泡法要大大小于冒泡法。2.算2法分析：1，分析双向起泡排序与传统的起泡排序非常相似，只不过起泡排序对数据序列的扫描始终朝着一个方向，而双向起泡排序对数据序列的扫描是在两个方向上交替进行双向起泡排序算法设计难度略高于起泡排序，但它使排序效率在一定范围内有一定程度的提高.上述双向起泡排序算法至少需进行趟扫描，至多需进行一趟扫描，即在待排序数据初始有序（正序）

4、情况下，关键字的比较次数为”一1，数据的移动次数为0；在待排序数据初始逆序的情况下，关键字的比较次数为”（z/2最坏情况下，每一次比较均会发生数据的交换，即移动次数为4/.显然双向起泡排序与起泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同.2性.能测试比较由于渐进复杂度分析的方法不能区分具有相同时间复杂度的算法，因此需要进行进一步测试.有研究设计者对双向起泡排序和起泡排序算法进行27延0边大学学报（自然科学版）第27卷了性能对比测试，结果如表1所示.测试所用数据均为16位非负随机数.测试结果表明，双向起泡排序与起泡排序算法的平均移动次数始终相

5、同；而对随机给出的数据序列，双向起泡排序算法要比起泡排序算法的平均比较次数要少.由于测试程序的统计量不是运行时间，所以测试结果不依赖于具体计算机的软、硬件等环境因素，而仅与算法有关.虽然在不同的计算机硬件、软件环境下，对于不同的待排序数据序列，其运行时间的测试结果也会不同，但表中数据可以在一定程度上反映算法的性能.测试结果表明，当数据量不大时，双向起泡排序并不比起泡排序效率更高，这是由于双向起泡排序算法平均比较次数较少的优点不足以抵消其程序结构复杂所带来的额外开销，而当数据量较大时，双向起泡排序的时间性能则明显优于起泡排序运行时间的测试结果。2.3事例比较：初始关键字：493865977613

6、2746冒泡排序：4938659776132746第一趟结果：38496576132746(97)第二趟结果：384965132746(76)第三趟结果：3849132746(65)第四趟结果：38132746(49)第五趟结果：132738(46)第六趟结果：1327(38)第七趟结果：(13)(27)从图中可以看出,每一趟排序,关键字“最大”的记录漂浮到了水面上,关键字较小的记录在逐渐下沉,每一趟排序有一个关键字“最大”的记录漂浮到了水面4。那么能不能在一趟排序中,让关键字“最小”的也同时沉到水底呢？这就是以下我们要介绍的双向起泡排序法。双向起泡排序法的基本思想是,通过一趟排序,找出关键字

7、“最大”和“最小”的两个记录,关键字大的向上浮到水面,关键字小的向下沉到水底,再进行第二趟排序,找出关键字次大和次小的记录。双向起泡排序4938659776132746R8(R1!第一趟结果：1346496576382797R2!R7I第二趟结果：274649653876R3IR6(第三趟结果：38464965r4iR5I第四趟结果：4649双向起泡法和通常的冒抱法相比较,两者数据比较的次数基本相同,但数据交换的次数相差很大,双向起泡法要大大小于冒泡法。如对于10个记录的序列,若初始序列为“逆序”,用冒泡法进行排序时,第一趟排序,需进行9次比较,相应的也需9次交换,才能找到关键字最大的记录；采

8、用双向起泡排序法,进行一趟排序,需进行9次比较,1次交换,找到了关键字最大和最小的两个记录。采用冒泡法需进行9趟排序,而采用双向起泡法只需5趟就可以达到目的。因而从性能上讲,双向起泡排序法大大优于通常的冒泡法,特别是对于大量的数据,就更显其优越性。概.要设计双1向起跑排序流程图1)逆向起泡排序：）正向起泡排序：3类.中2成员变量和成员函数原型声明构/造/函数，建立排序数组，采用顺序存储结构实现双向起泡排序/算/法输出排好序的数组/详.细设计源1程序设计1)构造函数Sort:Sort(intr,intm,intn)/函数的传值调用显得尤为重要，这是函数的入口,注意形参中的参数必须和程序中的参数是

9、一致的，不然的话就会出现未定义coutvv实际输入的元素个数为vvnvv个vvendl;r0=0;for(inti=1;ivn+1;i+)/由于第一个数组元素置空，那么就会有一个元素无法进入数组导致，输入元素比实际的少一个，因此循环加1coutvv请输入你要是排序的第vvivv元素：；cinri;mi=ri;coutvv您输入的元素如下：；for(i=1;ivn+1;i+)coutvvrivv;coutvvendl;2)双向起泡排序函数voidSort:BiBubble(intr,intn)intflag,i,j;intcount=0;flag=1;while(flag=1)flag=0;i=

10、0;for(j=n-i;ji;j-)逆向起泡排序,这里的j为n-i从最后一个元素开始比较if(rj-1rj)flag=1;intm;m=rj;rj=rj-1;rj-1=m;count+;/发生了交换，故将交换标志置为真for(j=i+1;jvn-i-1;j+)/正向起泡排序if(rjrj+1)flag=1;ints;s=rj;rj=rj+1;rj+1=s;count+;i+;coutvv比较的次数是：vvcountvvendl;3)输出排好序的数组voidSort:print(intn,intr)for(inti=1;in+1;i+)coutrin;Sorts(a,b,n);s.BiBubbl

11、e(a,n);s.print(n,a);coutvvendl;测.试数据及其结果分析5.系1统功能测试的数据和测试结果测试一：以二鸭:蚩一當:型阳蚩马率壷蚩：番霧:黑谨（70.gTOSSOO0Ofinqsa偉母IQSJDOSOIOSOO旳厢呈猱：密YY1Vfi:军匕一一-2*9丄5-封9uiT-6:MMMM6HsEKTsTMnznznznzH:tmbss占.占.T.9八.6:二叼，-19mmmm54多對MY旳郢壬曇至至至巫曰MS5iw#s4:-回hMMMW嗥毎hS蚩蚩蚩wBrJostEKTsVYYYkftB:.阵丰.丰丰丰圭-M-4SO硕08Eoo0oenqa因華回io8?dobotosoos

12、oVK鶴冋彖i：r”第四次：04367第五次：03467结果与预计结果相符。2）测试二：94617预计结果：14679需要比较次数：6TOC o 1-5 h z第一次：94167第二次：91467第三次：19467第四次：14967第五次：14697第六次：14679结果与预计结果相符，由此得知，此函数是可以进行双向起泡排序的6调.试过程中的问题6.1将起泡法改进为双向起泡排序算法起泡法，一般都是一次循环找到最大数，然后第二次循环找到次大数，以此类推，从而得到一个从小到大的排序结果。然而这样的排序所用的时间相比较长。我从起泡排序的基础上，对程序进行一定修改，把正向与反向排序结合起来，在一个大循环里运行小循环，从而缩短了时间，尤其在所要进行一次大数目的排序任务时。分析上面的程式段我们能够发现反向起泡时第一次循环找出了最小数，正向起泡第一次循环找到最大数。很显然在一次循环中即能够找到一个最小的数还能够找到一个最大的数，所以用双向冒泡排序的交换的次数减少了，从而达到了优化起泡法的作用。专.业课程设计总结通过本次课程设计，我所做的作业双向起泡排序算法，让我更深入的理解了排序算法，从刚开始的需求分析，我在以前的数据结构书中寻找算法思