基于VB的排序算法比较

《基于VB的排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于VB的排序算法比较（陈先红湖北省仙桃市沔城高级中学）摘要：排序在程序设计中占有很重要的地位,排序算法的好坏,直接影响到程序的时间复杂度.本文通过VB设计出一个程序,用来直观地比较各种排序的优劣.关键词：排序算法时间复杂度程序设计中图类分号:TP312文献标识码:ATheComparisonofSortingAlgorithmsBasedonVBAbstract:Sortingisimportanttoprogramming.Thesortingalgorithmhasgreatinfluenceonthetimecomplexityoftheprobl

2、em.AprogrammingbasedonVBisdesignedandmanysortingalgorithmsarecomparedinthearticle.Keywords:sortingalgorithm;timecomplexity;programming1.引言排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素（或记录）的任意序列,重新排列成一个按关键字有序的序列.在计算机数据处理中,特别是在事务处理中,排序(Sorting)占了很大的比重,一般认为有1/4的时间用在排序上,而对安装程序,多达50%的时间花费在对表的排序上.计算机

3、在处理过程中,有大量时间用于排序和查找工作上.因此,研究各种排序方法是计算机工作者的重要工作之一.2.各种算法思想2.1冒泡排序(BubbleSort):即首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换之,然后比较第二个记录和第三个记录的关键字.依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止.上述过程称做第一趟起泡排序,其结果是使关键字最大的记录被安置到最后一个记录的位置上.然后进行第二趟起泡排序,对前n-1个记录进行同样操作,其结果是使关键字次大的记录被安置到第n-1个记录的位置上.重复上述过程直到“在一

4、趟排序过程中,没有进行过交换的记录操作”.2.2简单选择排序(SimpleSelectionSort)：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录.一趟简单选择简单排序的操作为：通过n-i次关键字间的比较,从n-i-1个记录中选出关键字最小的记录,并和第i（1=

5、序的操作为：在含有i-1个记录的有序子序列r[1..i-1]中插入一个记录r[i]后,变成含有i个记录的有序子序列r[1..i]；并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r[0]处设置监视哨.在自i-1起往前搜索的过程中,可以同时后移记录；整个排序过程为进行n-1趟插入,即：先将序列中第1个记录看成是一个有序的子序列,然后从第2个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止.2.4希尔排序(Shell’sSort):希尔排序方法又称为缩小增量排序.该方法的基本思想是：先将整个待排记录序列分割成为若干个子序列分别

6、进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序.至此,希尔排序结束,整个序列的记录已经按关键字非递减有序排列.2.5快速排序（QuickSort）:快速排序是冒泡排序的改进算法.它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序.2.6堆排序（HeapSort）:堆排序分为两个步骤：第一步,根据初始输入数据,利用堆的调整算法形成初始堆,第二步,通过一系列的对象交换和重新调整堆进行排序.最大堆的第一个对象V[0

7、]具有最大的关键码,将V[0]与V[n]对调,把具有最大关键码的对象交换到最后,再对前面的n-1个对象,使用堆的调整算法,重新建立最大堆.结果具有次最大关键码的对象又上浮到堆顶,即V[0]位置.再对调V[0]和V[n-1].如此反复执行,最后得到全部排序好的对象序列.2.7归并排序(MergingSort):“归并”的含义是将两个或两个以上的有序表组合成一个两个或两个以上的有序表组合成一个新的有序表.假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到个长为2或1的有序子序列,再两两归并,......,如此重复,直

8、至得到一个长度为n的有序序列为止,这种排序方法称为2-路归并排序.