用VB实现的冒泡排序算法的分析与优化

通过对冒泡排序算法的分析,指出了其效率不高的缺陷,给出了三种优化的方法,它们能有效地提高排序算法的执行效率,并使用Visual Basic算法语言编程实现了这三种改进方法。

7 0

福

建电

脑

2 1年第 3期 01

用V B实现的冒泡排序法的分析与优化算刘模群(常州工学院计算机信息工程学院江苏常州 2 3 0 10 2)【摘要】通过对冒泡排序算法的分析，出了其效率不高的缺陷，出了三种优化的方法，:指给它们能有效地提高排序算法的执行效率 .并使用 V sa B s i l ac算法语言编程实现了这三种改进方法。 u i

【键词】冒泡排序；法分析；化关：算优1问题的提出、

( )此类推……, 4依在第 i的比较中，经过 n i轮要—排序是计算机科学中的一项复杂而重要的技术 .次相邻的两两比较，找出第 i的元素； 大 n个元素一共

其功能是对一个数据元素集合或序列重新排列成一个经过 n 1轮扫描，一最后剩下一个元素已在其正确位置， 按关键字有序的序列。冒泡排序是比较典型且常用的扫描区域最终为有序区排序算法。其基本思想是：于无序序列。两比较相 22算法设计对两 .邻数据的关键字，反序则进行交换，到没有反序为若直以上算法要注意的是 .每轮扫描都是从无序区自 止。在传统的冒泡排序算法中，管排序过程中序列的上面至该区间底部进行。第 i不轮扫描前，(…n i a a1—) 和 f—+…n分别为当前的无序区和有序区； i n il )第轮扫描变化情况 . n个元素排序一律进行 n 1轮比较 . i对一第轮中进行 n i—次两两比较找出目前最大 (最小 )或的一时 .当前的最大值元素””将沉到该区中的底部位置 a 个元素这样比较有时效率较低，以通过一定的方法 (—),可 n i使得 an i )上 (… n变为新的有序区。 下面用 V sa B s i l ai言设计实现了冒泡排序的 u c语减少关键字的比较次数，而提高该算法的执行效率。从 如何解决这一问题呢？可以充分利用每一轮比较中是算法，用排序子程序过程 S r来实现。中 a为待排序 ot其

否有数据交换的信息 .以及数据交换发生时的位置信的数组 . n为该数组的上界。 ()r a u 0 ((A tgr 1 i t Sbsn a) sI ee) Pve n 息 .改进和优化常规的冒泡排序算法。来

2算法设计和分析、() Dm nA tgrt s nee 2 i s nee, t r I AI g () n=U o n() 3 B u da()F ri 1T 4 o= on一1

21法描述和步骤 .算算法描述：待排序的数据放在数组 a1 1,将 (…n中 n个元素依次垂直排列，每个元素看作是重量为其值 ai f 1 的气泡根据轻气泡不能在重气泡之下的原则 .从上往下扫描数组 a凡扫描到违反本原则的重气泡，:就使其向下沉如此反复进行，到最后任何两个气泡都是轻、直者在上.重者在下为止。

() F r 5 o j=1T on—i

() 6

Ⅱa ) (+1 T e 0>ai ) h n

() 7() 8

t 0: 0=a=a)8 ) ( )ai ) j+1:(+1=tE dⅡ n

() N x j 9 et ( et 1 N xi 0O)n u】 dS b E

实现步骤：失一般性，们假定数组按照从小到 23算法分析不我 .大进行升序排序。 冒泡排序算法的时间复杂度主要依赖于关键字的 ()始： 1初 a数组的 1个元素为无序区， 3每轮都是自比较次数和数组元素的交换次数。 上而下进行扫描。 最好时间复杂度：如果初始序列是正序的，ot S r还 ( )一轮扫描：次比较相邻的两个元素。发是需要进行 n 1轮扫描 . 2第依若一但没有元素移动，需的关键所

现值大者在上、小者在下，交换两者的位置；过字比较次数 C和元素移动次数 M均达到最小值：=值则经 C n 1次相邻的两两比较后 .一轮扫描完毕时”重” n一 ), m=,以其最好的时间复杂度为 0n。—第最 ( 12 M 0所 n/ () 2的气泡就”底”沉到该区间的最下面 .即值最大的元素最坏时间复杂度：果初始序列是反序的，要进如需放到最后一个位置 a f) n,值较小的元素逐渐向上”漂行 n 1轮扫描每轮扫描时关键字的比较次数为 n i一—次 (≤i一 1且每次比较都必须移动数据 3次来达 1≤n 1, ( )二轮扫描：去已排好序的最大元素。剩到交换元素位置。 3第除对在这种情况下。比较和移动次数均达下的 n 1一个元素采用上述方法继续比较 .经过

n 2次到最大值：= (一 ),一 C nn 1 2 M一= nn 1 2所以其最坏的/ 3 (一 ),/浮”。

相邻的两两比较后 .值次大的元素放到了倒数第二个时间复杂度为 O n) f2。位置 an 1。 f一 ) 平均时间复杂度：假设输入序列的关键字的分布