双向起泡的排序算法VIP

双向气泡的排序算法1.主题的内容和要求1.1主题内容：双向冒泡排序算法，即两个相邻的路径冒泡方向相反。双向气泡排序法在两个方向浮动。通过一次排序，可以找到关键字“最大”和“最小”的两条记录，与冒泡算法相比，大大提高了速度。1.2要求1)设计一个排序算法，通过一个循环获得两端的最大值和最小值。2)与发泡法相比，时间性能应该有很大的突破。1.设计理念分析2.1基本理念气泡分选的基本思想冒泡排序很容易合并冒泡排序算法，即推回最大数量。排序后的记录数组R1.n垂直排列，每个记录Ri被认为是一个重量为Ri的气泡。根据轻气泡不能在重气泡下的原理，阵列r从下到上扫描：违反这个原理的轻气泡向上“漂浮”。重复这个过程，直到最后两个气泡是上面的轻气泡和下面的重气泡。一般来说，在I通道处理过程中，不需要检查I位置上方的元素，因为它们在先前的i-1通道处理之后已经被正确地排列。也就是说，在要排序的一组数据中，成对地比较数据的大小，并且当发现两个记录的排序顺序相反时，交换位置，直到没有相反顺序的记录。也就是说，它反复访问要排序的序列，一次比较两个项目，如果它们的顺序不对，就交换它们。重复访问序列的工作，直到不需要进行任何交换操作，并且序列已经被排序。一个气泡至少可以将具有最大值的元素发送到最后一个位置(或顶部位置)；当然，也可以反过来进行，将小值的元素向前或向下移动，并冒泡一次，至少可以将最小值的元素发送到最前面的位置(或最下面的位置)。双向气泡排序算法双向冒泡排序是冒泡排序的升级版本。双向冒泡排序可以在一个周期内同时达到最大值和最小值，减少了使用双向冒泡排序的交换次数，从而达到优化冒泡方法的效果。双向冒泡方法与普通冒泡方法基本相同，但是数据交换的数量有很大不同。双向鼓泡法比鼓泡法小得多。2.2算法分析：1.分析表明，双向冒泡排序与传统冒泡排序非常相似，只是冒泡排序对数据序列的扫描总是在一个方向上进行，而双向冒泡排序对数据序列的扫描是在两个方向上交替进行的。双向冒泡排序算法的设计难度略高于冒泡排序算法，但在一定范围内一定程度上提高了排序效率。上述双向气泡排序算法需要至少一次扫描，最多n次扫描，即在待排序数据为初始顺序(正顺序)的情况下，关键字的比较数为“1”，数据移动数为0；在要排序的数据的初始逆序的情况下，关键字比较的数量是“(z-1)/2”。在最坏的情况下，每次比较都会进行数据交换，即移动次数为3n ( 1)/2。显然，双向冒泡排序算法具有与冒泡排序算法相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字比较和移动次数完全相同。2.性能测试比较由于渐进复杂性分析方法不能区分具有相同时间复杂性的算法，因此需要进一步的测试。一些研究设计人员对延边大学学报(自然科学版)第27卷的双向冒泡排序和冒泡排序算法进行了性能对比测试，结果见表1。测试中使用的数据都是16位非负随机数。测试结果表明，双向冒泡排序和冒泡排序算法的平均移动次数总是相同的。对于随机给定的数据序列，双向冒泡排序算法比冒泡排序算法具有更少的平均比较。由于测试程序的统计不是运行时间，所以测试结果不依赖于环境因素，如特定计算机的软件和硬件，而只与算法有关。虽然在不同的计算机硬件和软件环境下，运行时间的测试结果会因要排序的不同数据序列而不同。但是，表中的数据可以在一定程度上反映算法的性能。测试结果表明，当数据量较小时，双向冒泡排序并不比冒泡排序更有效。这是因为双向冒泡排序算法的平均比较时间较少的优点不足以抵消其程序结构复杂性导致的额外开销，而当数据量较大时，双向冒泡排序的时间性能明显优于冒泡排序运行时间的测试结果。2.3案例比较：初始关键字：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。在一个排名中，“最小的”关键词能同时下降到底部吗？这是我们将在下面介绍的双向气泡排序方法。双向冒泡排序法的基本思想是通过一次排序找出关键字为“最大”和“最小”的两条记录。大的关键词浮到水面，小的关键词沉到水底。然后进行第二遍排序，找出具有第二大关键字和第二小关键字的记录。双向气泡分类49 38 65 97 76 13 27 46R1 R8第一次旅行的结果：13 46 49 65 76 38 27 97R2 R7第二次旅行结果：27 46 49 65 38 76R3 R6第三次旅行的结果：38 46 49 65R4 R5第四次旅行的结果：46 49双向发泡法与普通发泡法相比，两种方法的数据比较次数基本相同，但数据交换次数有很大差异，双向发泡法比发泡法小得多。例如，对于10条记录的序列，如果初始序列是“逆序”，当用冒泡法排序时，第一个序列需要进行9次比较，相应的序列需要进行9次交换才能找到具有最大关键字的记录。采用双向冒泡排序法，一次排序需要九次比较和一次交换，找到关键字最大和最小的两条记录。鼓泡法需要9次分选，而双向鼓泡法只需要5次即可达到目的。因此，就性能而言，双向冒泡排序法要比通常的冒泡排序法好得多，特别是对于大量的数据，它显示了它的优越性。3.轮廓设计3.1双向启动顺序流程图：1)反向气泡分选：jiYYN变量初始值：m=0数数j -标志=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中成员变量和成员函数的原型声明排序(int r，int m，int n)；/构造函数，建立排序数组，并采用顺序存储结构实现void Biubble(int r，int n)；/双向气泡排序算法无效打印(int n，int r)；/输出有序数组4.详细设计4.1源程序设计1)构造函数SORT :3360SORT (INTR ，INTM ，INTN)/函数的值传递调用尤为重要。这是函数的入口。请注意，形式参数中的参数必须与程序中的参数一致，否则会有未定义“Cout”实际输入的元素数是“ri”;mI=rI；您输入的元素如下：；对于(I=1；j-)/反向冒泡排序，其中j是n-i，从最后一个元素开始if(rj-1rj)标志=1；int m；m