数据结构及应用算法教程（修订版） 第3章 排序习题.ppt

《数据结构及应用算法教程（修订版） 第3章 排序习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章排序习题本章要点回顾:1.了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。2.掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。3.按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(nlogn)的高效排序方法和O(d×n)的基数排序方法。4.理解排序方法“稳定”或“不稳定”的

2、含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。排序方法:插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。如：插入、Shell排序交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。如：起泡、快速排序选择类从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。如：选择、堆排序归并类通过“归并”两个或两个以上的记录有序子序列，

3、逐步增加记录有序序列的长度。如:归并排序其它方法如:基数排序各种排序方法的综合比较:一、时间性能1.平均的时间性能时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：插入排序、起泡排序和选择排序时间复杂度为O(n):基数排序2.当待排记录序列按关键字顺序有序时:直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2);简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。二、空间性能指的是排序过程中所需的辅助空间大小所有的简单排序方法(

4、包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；快速排序为O(nlogn),为递归程序执行过程中，栈所需的辅助空间；归并排序所需辅助空间最多，其空间复杂度为O(n)。三、排序方法的稳定性稳定的排序方法指的是,对于两个关键字相等的记录，它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。3.对于不稳定的排序方法，只要能举出一个实例说明即可。例:对{4,3,4,2}进行快速排序结果{2,3,4,4}4.快速排序、堆排序和

5、希尔排序是不稳定的排序方法补充：希尔排序（又称缩小增量排序D.L.shell）基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整所谓“宏观”调整，指的是“跳跃式”的插入排序。具体做法：将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将n个记录分成d个子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}其中，d称为增量，它的值在排序过程中从

6、大到小逐渐缩小，直至最后一趟排序减为1。例如：第一趟希尔排序，设增量d=5第二趟希尔排序，设增量d=3第三趟希尔排序，设增量d=11625123047112336091831112312091816253630473109181211231625313047360911121618232530313647voidShellInsert(SqList&L,intdk)//一趟增量为dk的排序{for(i=dk+1;i<=n;++i)if(L.r[i].key

7、];//暂存在R[0]for(j=i-dk;j>0&&(L.r[0].key

8、ellInsert(SqList&L,intn)//一趟增量为dk的排序{k=n/2;while(k>=1){for(i=k+1;i<=n;++i)if(L.r[i].key0&&(L.r[0].key