《数据结构及应用算法教程（修订版） 第3章 排序习题》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 第3章 排序习题（22页珍藏版）》请在金锄头文库上搜索。
1、第3章 排序习题,本章要点回顾: 1.了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归 并排序和基数排序等五类。 2.掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和 最坏情况的时间性能。,3. 按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(nlogn)的高效排序方法和 O(dn)的基数排序方法。 4. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。 排序方
2、法: 插入类 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。如：插入、Shell排序,交换类 通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。如：起泡、快速排序 选择类 从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。如：选择、堆排序 归并类 通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。如:归并排序 其它方法 如:基数排序,各种排序方法的综合比较: 一、时间性能 1.平均的时间性能 时间
3、复杂度为 O(nlogn)：快速排序、堆排序和归并排序 时间复杂度为 O(n2)：插入排序、起泡排序和选择排序 时间复杂度为 O(n):基数排序 2.当待排记录序列按关键字顺序有序时:直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2);简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小,所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为O(1)；快速排序为O(nlogn),为递归程序执行过程中，栈所需的辅助空间；归并排序所需辅助空 间最多，其空间复杂度为 O(n
4、)。 三、排序方法的稳定性 稳定的排序方法指的是,对于两个关键字相等的记录，它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。 2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。例 : 对 4, 3, 4, 2 进行快速排序结果 2, 3, 4, 4 4. 快速排序、堆排序和希尔排序是不稳定的排序方法,补充：希尔排序（又称缩小增量排序 D.L.shell） 基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整 所谓“宏观”调整，指的是“跳跃式”的插入排序。 具体做法： 将记录序列分成若干子序列，分别
5、对每个子序列进行插入排序。 例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。 例如：,第一趟希尔排序，设增量 d =5,第二趟希尔排序，设增量 d = 3,第三趟希尔排序，设增量 d = 1,void ShellInsert ( SqList / 插入 / if / ShellInsert,void ShellSort (SqList /一趟增量为dltak的插入排序 / ShellSort,v
6、oid ShellInsert ( SqList /while / ShellInsert 时间复杂度：O(n1.3)，空间复杂度：O(1) 稳定性：不稳定，如：6 7 5 2 5 8 排序后：2 5 5 6 7 8,习题 3.2 答：稳定的排序方法:插入、选择、起泡、归并、基数排序 不稳定的排序方法:快速排序、堆排序、希尔排序 如：2 2 1 快速排序结果：1 2 2 4 3 4 2 堆排序结果：2 3 4 4 2 2 1 希尔排序结果: 1 2 2 习题 3.3 void Select_Sort(LinkList ,if(L-next) for(p=L-next;p;p=p-next) t
7、=p,s=p,x=t-data; for(q=p-next;q;q=q-next) if (q-datadata; s=q; if(s!=t) /找到了值比p-data更小的最小结点s temp=s-data; s-data=t-data; t-data=temp; /for /Select_Sort,习题 3.4 void Insert_Sort1(SqList ,while(change) change=0; for(i=1;ia.ri+1.key) a.r0=a.ri; a.ri=a.ri+1; a.ri+1=a.r0; change=1; for(i=2;ia.ri+1.key) a.
8、r0=a.ri; a.ri=a.ri+1; a.ri+1=a.r0; change=1; /while /OE_Sort 算法的结束条件是连续两趟比较无交换发生,习题 3.7 (1) 需2趟排序：6次；4次 共10次 (2) 4 5 3 6 1 2 7 2 1 3 4 6 5 7 1 2 3 4 5 6 7 or 15 50 10 1 30 18 2 17 13 16 12 20 18 23 习题 3.8 相邻两趟向相反方向起泡的冒泡排序算法 void BubbleSort2(sqlist /冒泡的上下界,while(lowl.ri+1.key) l.r0=l.ri; l.ri=l.ri+1;
9、 l.ri+1=l.r0; change=1; /有交换，修改标志change high-; /修改上界 for(i=high;ilow;i-) /从下向上起泡 if(l.ri.keyl.ri-1.key) l.r0=l.ri; l.ri=l.ri-1; l.ri-1=l.r0; change=1; low+; /修改下界 ,补充习题: 1.在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的是（ ）。 A）插入排序 B）冒泡排序 C）选择排序 D）堆排序 2.在各种排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的
10、方法，称为（ ）。 A）希尔排序 B）冒泡排序 C）插入排序 D）选择排序 3.快速排序方法在（）情况下最不利于发挥其长处。 A）要排序的数据量太大 B）要排序的数据含有多个相同值 C）要排序的数据已基本有序 D）要排序的数据个数为奇数,1.C 2.C 3. C,补充习题: 4.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，经过一趟冒泡排序后的序列为（）。 A）16，28，34，54，73，62，60，26，43，95 B）28，16，34，54，62，73，60，26，43，95 C）28，16，34，54，62，60，73，26
11、，43，95 D）16，28，34，54，62，60，73，26，43，95 5.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为（ ）。 A）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79,4.B 5.C,补充习题: 6.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)20,15,21,25,47,27,68,35,84 (2)15,20,
12、21,25,35,27,47,68,84 (3)15,20,21,25,27,35,47,68,84 则所采用的排序方法是（ ）。 A）选择排序 B）希尔排序 C）归并排序 D）快速排序 7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。 A）插入排序 B）快速排序 C）归并排序 D）选择排序,6.D 7.A,补充习题: 8.一组记录的排序码为（20,29,11,74,35,3,8,56）,则利用堆排序方法建立的初始(小顶)堆为（ ）。 A）20,29,11,74,35,3,8,56 B）3,29,8,56,35,11,20,74 C）3,8,11,20,29,35,56,74
13、 D）20,29,3,8,11,35,74,56 9.下列关键码序列中，属于堆的是（）。 A)（15，30，22，93，52，71） B)（15，71，30，22，93，52） C)（15，52，22，93，30，71） D)（93，30，52，22，15，71）,8.B 9.A,补充习题: 10.若要求尽可能快地对实数数组进行稳定的排序，则应选()。 A)快速排序 B)堆排序 C)归并排序 D)基数排序 11.下列排序算法的时间复杂度最小的是（）。 A)冒泡排序 B)希尔排序 C)简单选择排序 D)归并排序 12.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。 A)起泡排序 B)快速排序 C)堆排序 D)基数排序 13.插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。( ) A)正确 B)不正确,10.C 11.D 12.C 13.B,补充习题: 14.直接插入排序是不稳定的排序方法。( ) A)正确 B)不正确 15.直接插入排序的最坏情况是初始序列为（ ）序。 A)正 B)反 C)正和反 D)无 16.在各排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )。 A)希尔排序 B)归并排序 C)插入排序 D)选择排序,14.B 15.B 16.D,
