湘潭大学-数据结构-课件-ppt-Ch07-Sorting-排序算法.ppt

《湘潭大学-数据结构-课件-ppt-Ch07-Sorting-排序算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章排序——很常见的一类问题（并不局限于排序本身）§1预备知识voidX_Sort(ElementTypeA[],intN)/*N是排序元素个数，是合法的整数*//*为简单起见，假设数组只包含整数*//*‘>’和‘<’运算符存在，而且是仅有的允许对输入数据进行的操作*/基于比较的排序/*仅考虑内部排序*/整个排序工作能够在主存中完成§2插入排序voidInsertionSort(ElementTypeA[],intN){intj,P;ElementTypeTmp;for(P=1;P

2、){Tmp=A[P];/*thenextcomingcard*/for(j=P;j>0&&A[j-1]>Tmp;j--)A[j]=A[j-1];/*shiftsortedcardstoprovideapositionforthenewcomingcard*/A[j]=Tmp;/*placethenewcardattheproperposition*/}/*endfor-P-loop*/}最坏情形:输入的A[]是反序的。T(N)=O(N2)最好情形:输入的A[]是已预先排序的。T(N)=O(N)§

3、3一些简单排序算法的下界【定义】成员存数的数组的一个逆序是指数组中具有性质iA[j]的序偶（A[i]，A[j]）。〖例1〗输入数据34,8,64,51,32,21有个逆序。9(34,8)(34,32)(34,21)(64,51)(64,32)(64,21)(51,32)(51,21)(32,21)在插入排序中恰好需要执行次交换。9交换两个不按原序排列的相邻元素恰好消除一个逆序。T(N,I)=O()，I是初始数组中的逆序数。I+N如果数组几乎有序，这个时间是很快的。这就是全部结论?

4、那么怎么加速排序?嘿!我们讨论的是基于比较的排序，你必须进行比较，然后呢？这个定理告诉我们什么?聪明!为了使算法运行更快，我们必须在一次交换中不止消除一个逆序。…交换距离较远的元素？呃…散列?对一整类只交换相邻元素的算法来说，都需要花费O(N2)的时间来排序。§3一些简单排序算法的下界【定理】N个互异数的数组的平均逆序数是N(N1)/4.【定理】通过交换相邻元素进行排序的任何算法平均需要(N2)时间。§4希尔排序----byDonaldShell〖例2〗Sort:81941196123517

5、952858417515962812588135419417751195155-sort964194112858357595128117153-sort1-sort96419411285835759512811715定义一个增量序列h1

6、ElementTypeA[],intN){inti,j,Increment;ElementTypeTmp;for(Increment=N/2;Increment>0;Increment/=2)/*hsequence*/for(i=Increment;i=Increment;j-=Increment)if(Tmp

7、=Tmp;}/*endfor-Iandfor-Incrementloops*/}§4希尔排序最坏情形分析:【定理】使用希尔增量的希尔排序的最坏运行时间是(N2)。〖例3〗一个坏例子:19210311412513614715816192103114125136147158168-sort192103114125136147158164-sort192103114125136147158162-sort123456789101112131415161-sort增量对未必互素，因此较小的增量可能影

8、响很小。§4希尔排序Hibbard增量序列:hk=2k1----相邻增量没有公因子。【定理】使用Hibbard增量的希尔排序的最坏情形运行时间为(N3/2).猜测：Tavg–Hibbard(N)=O(N5/4)Sedgewick的最好增量序列是{1,5,19,41,109,…}，该序列中的项要么是94i–92i+1，或者是4i–32i+1。猜测其平均运行时间Tavg(N)=O(N7/6)，最坏情形运行时间Tworst(N)=O(N4/3).希尔排序算法的整体时间复杂度和增量序列的