双向起泡的排序算法

**双向起泡的排序算法1.课题内容和要求1.1课题内容：双向起泡的排序算法，即相邻两遍向相反的方向起泡。精品文档放心下载双向起泡排序法，向两个方向漂浮，通过一趟排序，可找出关键字“最大”和“最小”感谢阅读的两个记录，因而相比起泡算法速度大大提高了．1.2要求1）设计一个排序算法，使之拥有通过一次循环使两端得到最大数最小数的功能感谢阅读2）与起泡法相比较，在时间性能上要有一个很大的突破设计思路分析2.1基本思想起泡排序的基本思想起泡排序易于冒泡排序算法合并，即向后推出最大数。将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i]的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。一般地，第i遍处理时，不必检查第i个位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。即就是在一组待排序的数据中，两两比较数据的大小，发现两个记录的排序次序相反时就交换位置，直到没有反序的记录为止。也就是说它重复地走访过要排序的序列，一次比较两个项目，如果他们的顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有再需要做交换动作，该序列已经排序完成。一趟冒泡，至少可以把值最大的元素送到最后位置谢谢阅读**(或最上边)；当然也可以倒过来做，把值小的元素向前移或向下移，一趟冒泡，至少可以精品文档放心下载把值最小的元素送到最前面的位置(或最下边)。双向起泡排序算法思想双向起泡排序是冒泡排序的升级版，双向起泡排序连够在一次循环中同时取得最大感谢阅读值与最小值，所以用双向冒泡排序的交换的次数减少了，从而达到了优化起泡法的作用。感谢阅读双向起泡法和通常的冒泡法比较，两者比较次数基本相同，但数据交换的次数相差很大，精品文档放心下载双向起泡法要大大小于冒泡法。2.2算法分析：1，分析双向起泡排序与传统的起泡排序非常相似，只不过起泡排序对数据序列的扫描始终朝着一个方向，而双向起泡排序对数据序列的扫描是在两个方向上交替进行．双向起泡排序算法设计难度略高于起泡排序，但它使排序效率在一定范围内有一定程度的提感谢阅读高．上述双向起泡排序算法至少需进行1趟扫描，至多需进行n一1趟扫描，即在待排序数据初始有序(正序)情况下，关键字的比较次数为”一1，数据的移动次数为0；在待排序数据初始逆序的情况下，关键字的比较次数为”(z一1)／2，最坏情况下，每一次比较均会发生数据的交换，即移动次数为3n(～1)／2．显然双向起泡排序与起泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同．谢谢阅读2.性能测试比较由于渐进复杂度分析的方法不能区分具有相同时间复杂度的算法，因此需要进行进一步测试．有研究设计者对双向起泡排序和起泡排序算法进行270延边大学学报(自然科学版)第27卷了性能对比测试，结果如表1所示．测试所用数据均为16位非负随机数．测试结果表明，双向起泡排序与起泡排序算法的平均移动次数始终相同；而对随精品文档放心下载**机给出的数据序列，双向起泡排序算法要比起泡排序算法的平均比较次数要少．由于测试感谢阅读程序的统计量不是运行时间，所以测试结果不依赖于具体计算机的软、硬件等环境因素，感谢阅读而仅与算法有关．虽然在不同的计算机硬件、软件环境下，对于不同的待排序数据序列，谢谢阅读其运行时间的测试结果也会不同，但表中数据可以在一定程度上反映算法的性能．测试结谢谢阅读果表明，当数据量不大时，双向起泡排序并不比起泡排序效率更高，这是由于双向起泡排感谢阅读序算法平均比较次数较少的优点不足以抵消其程序结构复杂所带来的额外开销，而当数据感谢阅读量较大时，双向起泡排序的时间性能则明显优于起泡排序运行时间的测试结果。精品文档放心下载2.3事例比较：初始关键字： 49 38 65 97 76 13 27 46精品文档放心下载冒泡排序：4938659776132746第一趟结果：38496576132746(97)第二趟结果：384965132746(76)第三趟结果：3849132746(65)第四趟结果：38132746(49)第五趟结果：132738(46)第六趟结果：1327(38)第七趟结果：(13)(27)从图中可以看出,每一趟排序,关键字“最大”的记录漂浮到了水面上,关键字较小的记录在逐渐下沉,每一趟排序有一个关键字“最大”的记录漂浮到了水面4。那么能不能在一趟排序中,让关键字“最小”的也同时沉到水底呢？这就是以下我们要介绍的双向起泡排序法。精品文档放心下载**双向起泡排序法的基本思想是,通过一趟排序,找出关键字“最大”和“最小”的两个记录,关键字大的向上浮到水面,关键字小的向下沉到水底,再进行第二趟排序,找出关键字次大和次小的记录。感谢阅读双向起泡排序4938659776132746R1↓R8↓第一趟结果：1346496576382797R2↓R7↓第二趟结果：274649653876R3↓R6↓第三趟结果：38464965R4↓R5↓第四趟结果：4649双向起泡法和通常的冒抱法相比较,两者数据比较的次数基本相同,但数据交换的次数相差很大,双向起泡法要大大小于冒泡法。如对于10个记录的序列,若初始序列为“逆序”,用冒泡法进行排序时,第一趟排序,需进行9次比较,相应的也需9次交换,才能找到关键字最大的记录；采用双向起泡排序法,进行一趟排序,需进行9次比较,1次交换,找到了关键字最大和最小的两个记录。采用冒泡法需进行9趟排序,而采用双向起泡法只感谢阅读5趟就可以达到目的。因而从性能上讲,双向起泡排序法大大优于通常的冒泡法,特别是对于大量的数据,就更显其优越性。谢谢阅读3.概要设计**3.1双向起跑排序流程图：1)逆向起泡排序：开始变量赋初值：i=0，j=n-1Ni<=ni=i+1Nj>i输出排好序的数组Yj--r[j]r[j-1]>r[j]N结束Yflag=变量赋初值：m=0m=r[j]r[j]=r[j-1]Count++j--2）正向起泡排序：**开始变量赋初值：i=0，j=n-1i=i+1N

Ni<=nj<n-i-1Y j++r[j]>r[j+1]？Yflag=1

N

输出排好序的数组r[j]变量赋初值：s=0s=r[j]r[j]=r[j+1]r[j+1]=sCount++

结束**3.2类中成员变量和成员函数原型声明Sort(intr[],intm[],intn);精品文档放心下载//构造函数，建立排序数组，采用顺序存储结构实现voidBiBubble(intr[],intn);精品文档放心下载//双向起泡排序算法**voidprint(intn,intr[]);精品文档放心下载//输出排好序的数组4.详细设计4.1源程序设计1） 构造函数Sort::Sort(intr[],intm[],intn)//函数的传值调用显得尤为重要，这是函数的入口,注意形参中的参数必须和程序中的参数是一致的，不然的话就会出现未定义{cout<<"实际输入的元素个数为"<<n<<"个"<<endl;r[0]=0;for(inti=1;i<n+1;i++)//由于第一个数组元素置空，那么就会有一个元素无法进入数组导致，输入元素比实际的少一个，因此循环加1谢谢阅读{cout<<"请输入你要是排序的第"<<i<<"元素：";精品文档放心下载cin>>r[i];m[i]=r[i];}cout<<"您输入的元素如下：";for(i=1;i<n+1;i++)cout<<r[i]<<"";cout<<endl;**}2)双向起泡排序函数voidSort::BiBubble(intr[],intn)精品文档放心下载{intflag,i,j;intcount=0;flag=1;while(flag==1){flag=0;i=0;for(j=n-i;j>i;j--) //逆向起泡排序,这里的j为n-i从最后一个元素开始比较谢谢阅读{if(r[j-1]>r[j]){flag=1;intm;m=r[j];r[j]=r[j-1];r[j-1]=m;count++;} //发生了交换，故将交换标志置为真**}for(j=i+1;j<n-i-1;j++) //正向起泡排序谢谢阅读{if(r[j]>r[j+1]){flag=1;ints;s=r[j];r[j]=r[j+1];r[j+1]=s;count++;}}i++;}cout<<"比较的次数是："<<count<<endl;谢谢阅读}3）输出排好序的数组voidSort::print(intn,intr[])感谢阅读{**for(inti=1;i<n+1;i++)cout<<r[i]<<"";}4）mian函数voidmain(){intb[MaxSize]; //辅助初始数组inta[MaxSize]; //待排序数组intn; //全局变量以便调用cout<<"请输入你需要双向起泡排序的数据的个数：";感谢阅读cin>>n;Sorts(a,b,n);s.BiBubble(a,n);s.print(n,a);cout<<endl;}5.测试数据及其结果分析5.1系统功能测试的数据和测试结果测试一：**测试二：5.2结果分析1）测试一：47036预计结果为：03467需要进行5次比较：47036**第一次：40736第二次：04736第三次：04376第四次：04367第五次：03467结果与预计结果相符。2）测试二：94617预计结果：14679需要比较次数：6第一次：94167第二次：91467第三次：19467第四次：14967第五次：14697第六次：14679结果与预计结果相符，由此得知，此函数是可以进行双向起泡排序的。谢谢阅读6.调试过程中的问题6.1将起泡法改进为双向起泡排序算法**起泡法，一般都是一次循环找到最大数，然后第二次循环找到次大数，以此类推，从而得到一个从小到大的排序结果。然而这样的排序所用的时间相比较长。我从起泡排序的基础上，对程序进行一定修改，把正向与反向排序结合起来，在一个大循环里运行小循环，从而缩短了时间，尤其在所要进行一次大数目的排序任务时。谢谢阅读分析上面的程式段我们能够发现反向起泡时第一次循环找出了最小数，正向起泡第一次循环找到最大数。很显然在一次循环中即能够找到一个最小的数还能够找到一个最大的数，所以用双向冒泡排序的交换的次数减少了，从而达到了优化起泡法的作用。谢谢阅读7.专业课程设计总结通过本次课程设计，我所做的作业双向起泡排序算法，让我更深入的理解了排序算感谢阅读法，从刚开始的需求分析，我在以前的数据结构书中寻找算法思想，还在网上寻求他人的感谢阅