双向起泡的排序算法

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，分析双向起泡排序与传统的起泡排序非常相似，只不过起泡排序对数据序列的扫描始终朝着一个方向，而双向起泡排序对数据序列的扫描是在两个方向上交替进行.双向起 泡排序算法设计难度略高于起泡排序，但它使排序效率在一定范围内有一定程度的提 咼.上述双向起泡排序算法至少需进

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

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

6、，双向起泡排序的时间性能则明显优于起泡排序运行时间的测试结果。关键字“最大”的记录漂浮到了水面上，关键字较小的2.3事例比较:初始关键字：4938659776132746冒泡排序：4938659776132746第一趟结果：38496576132746(97)第二趟结果：384965132746(76)第三趟结果：3849132746(65)第四趟结果：38132746(49)第五趟结果：132738(46)第六趟结果：1327(38)第七趟结果：(13)(27)从图中可以看出，每一趟排序,记录在逐渐下沉，每一趟排序有一个关键字“ 最大”的记录漂浮到了水面 4。那么能不能在一趟排序中，让关键字

7、“最小” 的也同时沉到水底呢？ 这就是以下我们要介绍的双 向起泡排序法。双向起泡排序法的基本思想是，通过一趟排序，找出关键字“最大”和“最小”的两个记录，关键字大的向上浮到水面，关键字小的向下沉到水底,再进行第二趟排序，找出关键字次大和次小的记录。双向起泡排序49386597761327Ri ；第一趟结果：13464965763827R2；R7 J第二趟结果：274649653876R3 JR6 J第三趟结果：38464965R4 J R5 J第四趟结果：464946R8 J97双向起泡法和通常的冒抱法相比较，两者数据比较的次数基本相同，但数据交换的次数相差很大，双向起泡法要大大小于冒泡法。如

8、对于10个记录的序列，若初始序列为“逆 序”，用冒泡法进行排序时，第一趟排序，需进行9次比较，相应的也需9次交换，才能 找到关键字最大的记录；采用双向起泡排序法，进行一趟排序，需进行9次比较,1次交换,找到了关键字最大和最小的两个记录。采用冒泡法需进行9趟排序，而采用双向起泡法只 需5趟就可以达到目的。因而从性能上讲，双向起泡排序法大大优于通常的冒泡法，特别 是对于大量的数据，就更显其优越性。3. 概要设计3.1双向起跑排序流程图:1）逆向起泡排序:i=i+1fNi<=nNj>iNri-1>rjYc开始JI变量赋初值：i=0 ,，=n-1输出排好 序的数组rjr7结束）fla

9、g=变量赋初值：m=om=rj rj=rj-1Coun t+2 ）正向起泡排序:i=i+1c_开始）变量赋初值：i=0 , ,=n-1NNj<n-i-YYN_trl>ri+1flag=1J变量赋初值：s=0输出排好序的数组rffls=rj rj=rj+1 ri+1=s结束Coun t+I3.2类中成员变量和成员函数原型声明Sort(i nt r,i nt m,i nt n);/构造函数，建立排序数组，采用顺序存储结构实现void BiBubble(i nt r,i nt n);/双向起泡排序算法void prin t(i nt n ,i nt r);/输出排好序的数组4. 详细设计

10、4.1源程序设计构造函数Sort:Sort(i nt r,i nt m,i nt n)/函数的传值调用显得尤为重要，这是函数的入口 ，注意形参中的参数必须和程序中的参数是一致的，不然的话就会出现未定义cout<<" 实际输入的元素个数为"<< n<<" 个"<<e ndl;r0=0；for(i nt i=1;i< n+1;i+)/由于第一个数组元素置空，那么就会有一个元素无cout<<e ndl;法进入数组导致，输入元素比实际的少一个，因此循环加H.cout<<"请输

11、入你要是排序的第"<<i<<"元素:cin> >ri;mi=ri;cout<<"您输入的元素如下:H.for(i=1;i <n+1;i+)cout<<ri<<""2）双向起泡排序函数void Sort:BiBubble(i nt r,i nt n)int coun t=0;flag=1;while(flag=1)flag=O;i=O;II发生了交换，故将交换标志置为真for(j=n-i;j>i;j-)II逆向起泡排序，这里的j为n-i从最后一个元素开始比较if(

12、rj-1>r j)flag=1;int m;m=rj;r j=rj-1;r j-1=m;coun t+;/正向起泡排序for(j=i+1;j< n-i-1;j+)if(r j>rj+1)flag=1;int s;s=rj;rj=r j+1;rj+1=s;coun t+;i+;cout<<"比较的次数是："<<cou nt<<e ndl;3）输出排好序的数组 void Sort: prin t(i nt n ,i nt r)for(i nt i=1;i< n+1;i+)cout<<ri<<&q

13、uot;"4) mian函数/辅助初始数组/待排序数组void mai n() int bMaxSize;int aMaxSize;int n;/全局变量以便调用H.cout<<"请输入你需要双向起泡排序的数据的个数:cin>>n;Sort s(a,b, n);s.BiBubble(a, n);s.print(n ,a);cout<<e ndl;5. 测试数据及其结果分析5.1系统功能测试的数据和测试结果测试一:第一次:4 0 7 3 6*碍程设计卫 8 00 280103002301 何素婷 Debu g08002 8 咗電的框刑US

14、帏个元一兀元元_兀 书 51234S7 起的的的的S 雯元曰習習書書疋据 BSS要要要要_兀数数y A叟入入入入入的序. 请冥情请请请谙命住排 班4-70366307 iG n4 c3 0t0"I-T9 4-6177 .-旺元元元元6 J 5 1 2 3 4-54 置起眇眇眇抄= ©Hboytt 下97G4辱，.審输贬遢囂糯® . 道头请请请请请你疋排W t y 爭V n a s s e5.2结果分析1 ）测试一：4 7 0 3 6预计结果为：0 3 4 6 7需要进行5次比较：4 7 0 3 6第二次:第三次:第四次:第五次:结果与预计结果相符。2 ）测试二：9

15、 4 6 1 7预计结果：1 4 6 7 9需要比较次数：6第一次:第二次:第三次:第四次:第五次:第六次:结果与预计结果相符，由此得知，此函数是可以进行双向起泡排序的。6. 调试过程中的问题6.1将起泡法改进为双向起泡排序算法起泡法，一般都是一次循环找到最大数，然后第二次循环找到次大数，以此类推，从而得到一个从小到大的排序结果。然而这样的排序所用的时间相比较长。我从起泡排序的 基础上，对程序进行一定修改，把正向与反向排序结合起来，在一个大循环里运行小循环, 从而缩短了时间，尤其在所要进行一次大数目的排序任务时。分析上面的程式段我们能够发现反向起泡时第一次循环找出了最小数，正向起泡第一 次循环找到最大数。很显然在一次循环中即能够找到一个最小的数还能够找到一个最大的 数，所以用双向冒泡排序的交换的次数减少了，从而达到了优化起泡法的作用。7. 专业课程设计总结通过本次课程设计，我所做的作业双向起泡排序算法，让我更深入的理解了排序算法，从刚