《第9章内部排序》习题解答

1、第9章 内部排序第9章内部排序本章学习要点熟悉并掌握本章中各种内部排序方法的基本思想及其实现过程掌握各种内部排序算法的时间复杂度和空间复杂度的计算和分析方法了解各种内部排序方法的优缺点以及其不同的应用场合要求能够针对实际问题的特点选择合理的排序算法并通过编程实现排序（Sorting）是计算机程序设计中的一种重要运算，它的功能是将一组数据元素按照其关键字的某种规定顺序（递增或递减）进行排列。对数据元素进行排序的目的是为了便于查找，在关键字有序的一组数据中的查找要比无序时更容易，速度也更快。本章主要介绍几种常用的内部排序方法，主要有：插入排序、交换排序、选择排序、归并排序和基数排序。最后对各种排序

2、算法的时间复杂度和空间复杂度进行了分析和比较，并且讨论了如何针对实际问题合理选择排序算法等内容。9.1排序的有关概念和数组的输入与输出9.1.1排序的概念1排序将一个数据元素的任意序列，重新排列成一个按关键字有序（递增有序或递减有序）的序列的过程叫排序。2排序方法的稳定性若在排序过程中，序列的两个关键字值相同的记录的相对位置不发生改变，则称所用的排序方法为稳定的；反之，若在某个序列的排序过程中关键字值相同的记录的相对位置发生了改变，则称所用的排序方法是不稳定的。3内部排序和外部排序在排序过程中，如果待排序列全部读入计算机存储器中，则称此为内部排序；反之，若待排序列仅有部分记录在内存中，在排序过

3、程中还要对外存中的纪录进行访问，这样的排序过程叫外部排序。4排序方法的性能分析对于所选用的排序方法的好坏主要是基于其算法的时间复杂度和空间复杂度两方面进行分析。5数据元素类型说明数据元素可以是任意一个结构类型，排序过程是按元素中的某个关键字（数据项）进行排序。不失一般性，我们在本章的所有例题中总是假定待排序列中的数据元素中只含有关键字项，且其数据类型为整型。9.1.2一维数组的输入与输出1数组输入操作函数void Input(int *A,int n)的功能是，从键盘输入n个整数到数组A中。#includeiostream.hvoid Input(int *A,int n)int i;cout

4、请输入n个整数:n;for(i=0;iAi;2数组输出操作函数void Output(int A,int n)的功能是，依次显示输出数组A中的n个整数。void Output(int A,int n)int i;cout结果为:n;for(i=0;in;i+)coutAi ;coutendl;3数组排序操作函数void MainSort(void(*sort)(int*,int)的功能是，首先通过函数调用Input(A,n)输入n个整数到数组A中，再通过函数调用sort(A,n)对A中的n个整数排序，最后通过函数调用Out(A,n)显示输出数组A中的n个整数。void MainSort(voi

5、d(*sort)(int*,int)int *A,n;coutn;A=new intn;Input(A,n);cout原顺序;Output(A,n);sort(A,n); /调用sort对数组A进行处理cout排序后的顺序;Out(A,n);deleteA;9.2插入排序法9.2.1直接插入排序(Straight Insertion Sort)1算法思想对于任意排列的序列(a0,a1,a2,an-1)，先将第一个记录看成是一个有序序列L1=(a0)，再将第2个记录插入到L1中得到有序序列L2=(a0,a1)一般的，将第k+1个记录插入到有序序列Lk中得到有序序列Lk+1，如此重复插入n-1次即

6、可得到有序序列Ln=(a0,a1,a2,an-1)。2举例说明设原始序列为：8、3、5、2、9、7、*5、4-.294.-第1轮：(8) 3,5,2,9,7,*5,4第2轮：(3,8) 5,2,9,7,*5,4第3轮：(3,5,8) 2,9,7,*5,4第4轮：(2,3,5,8) 9,7,*5,4第5轮：(2,3,5,8,9) 7,*5,4第6轮：(2,3,5,7,8,9) *5,4第7轮：(2,3,5,*5,7,8,9) 4第8轮：(2,3,4,5,*5,7,8,9) 3算法实现void InsertSort(int A,int n)int temp,i,j;for(i=0;i0;j-)if

7、(temp=Aj-1)break;Aj=Aj-1;Aj=temp; /将temp插入到相应的位置4算法分析从排序过程可知该算法是稳定的；算法的比较次数为f(n)=1+2+3+n-1，所以该算法的时间复杂度为T(n)=O(n2)；由于在排序过程中仅有一个辅助变量（temp），所以该算法的空间复杂度为S(n)=O(1)。说明：（1）从算法的基本操作部分可以看出，当待排序数组An基本有序时可以大大减少其比较的执行次数，所以该算法适用于序列为基本有序的场合。（2）使用直接插入排序算法排序时可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。比如，初始序列的最后一个元素为最小元素时就会

8、出现以上情况。*9.2.2折半插入排序折半插入排序是直接插入排序的一个改进算法，该算法在排序过程中，通过折半查找法来实现寻找插入位置的操作，从而减少了数据元素中关键字的比较次数。1折半插入排序函数void InertSort1(int a,int n)int i,j,k,t,l,h;for(i=1;in;i+)if(aiai-1)l=0;h=i-1;while(l=h) /用二分法查找插入位置t=(l+h)/2;if(at=ai)break;else if(atai)l=t+1;else h=t-1;if(ht;j-)aj=aj-1;aj=k;2分步实现折半查找插入排序(1) 函数int Fo

9、und(int A,int n,int x)通过折半查找法求元素x在数组An中的插入下标。int Found(int A,int n,int x)int t,l,h;l=0;h=n-1;if(x=Ah)t=n;else if(x=A0)t=0;elsewhile(l=h)t=(l+h)/2;if(At=x)break;else if(Atx)l=t+1;else h=t-1;if(hl)t=l;return t;(2) 调用函数Found()实现插入排序。void InertSort2(int a,int n)int i,j,x,t;for(i=1;it;j-)aj=aj-1;at=x;9.2

10、.3 希尔排序法(Shell Sort)1算法思想先将整个待排的n个记录序列按照某个间隔值d1（通常取n/2）分割成为若干个子序列，再对其分别进行直接插入排序，下一步取间隔值d2d1（通常取di+1=di/2）重复前面的过程直到间隔值为1时对整体序列进行最后一次直接插入排序。2举例说明设原始序列为：7、5、9、13、10、2、3、*5、8、1，其长度为n=10。第1轮：取间隔值d=10/2=5，先将序列看成如图9.1(a)所示的5个子序列：(7,2)(5,3)(9,*5)(13,8)(10,1)。再分别对每个子序列进行插入排序，其结果为如图9.1(b)所示的子序列：(2,7)(3,5)(*5,

11、9)(8,13)(1,10)。第1轮排序结果为：2,3,*5,8,1,7,5,9,13,10（注意：在对各子序列排序时，子序列在主序列中的相对位置不变）。第2轮：取间隔值d=5/2=2，先将序列分成如图9.2(a)所示的2个子序列：(2,*5,1,5,13)(3,8,7,9,10)。再分别进行插入排序，其结果为如图9.2(b)所示的子序列：(1,2,*5,5,13)(3,7,8,9,10)。第2轮排序结果为：1,3,2,7,*5,8,5,9,13,10。第3轮：取d=2/2=1，此时将整体序列进行一次直接插入排序。第3轮排序结果为：1，2，3，*5，5，7，8，9，10，13。3算法实现(1)

12、 算法Insert(A,k,n)的功能是，对数组An按间隔k进行分组插入排序void Insert(int A,int k,int n)int i,j,temp;for(i=k-1;i=0;j-=k) /在相应的子序列中寻找插入位置。if(temp=Aj-k)break;Aj=Aj-k; Aj=temp; /将temp插入到相应的位置(2) 希尔排序函数void ShellSort(int A,int n)int k=n;while(k=k/2)Insert(A,k,n);4算法分析该算法是不稳定的；希尔排序算法的时间复杂度与间隔值d的取法有关，当取d1=n， di+1=di/2(i=1,2,

13、3,)时，该算法的时间复杂度为T(n)=O(nlog2n)，空间复杂度为S(n)=O(1)。9.3交换排序法交换排序是借助于交换操作来完成的排序方法。它的基本思想是：在待排序的序列中，找到不满足序性的两个关键字，交换相应元素的相对位置，以满足序性；重复该过程，直到序列中所有元素的关键字都有序为止。本节主要介绍最为常见的两个交换排序算法：起泡排序法和快速排序法。9.3.1起泡排序法(Bubble Sort)1算法思想(大数沉底法)起泡排序算法的基本思想是：先将第1个与第2个记录的关键字比较，如果关键字逆序，则交换这两个记录，否则不交换；再将第2个与第3个记录的关键字比较，如果关键字逆序，则交换第

14、2个与第3个记录，否则不交换，以此类推，最后将第n-1个与第n个记录的关键字比较，如果关键字逆序，则交换，否则不交换。上述过程称为一趟起泡排序，其结果是使关键字值最大的记录移到第n个记录的位置。然后对前n-1个记录进行同样的操作，第2趟起泡排序的结果是使关键字值次大的记录移到第n-1个记录的位置。一般地，第i趟起泡排序的结果是从前n-i个记录中将关键字最大的记录移到第n-i+1个记录的位置上。如果在某一趟排序中没有发生交换操作，则整个排序提前结束，否则最后排到仅剩一个记录为止。2举例说明设原始记录序列为：8、3、5、2、9、7、*5、4第1趟排序结果：3,5,2,8,7,*5,4,(9)第2趟

15、排序结果：3,2,5,7,*5,4,(8,9)第3趟排序结果：2,3,5,*5,4,(7,8,9)第4趟排序结果：2,3,5,4,(*5,7,8,9)第5趟排序结果：2,3,4,(5,*5,7,8,9)第6趟排序结果：2,3,(4,5,*5,7,8,9)由于没有发生交换操作，排序提前结束。3算法实现void BubbleSort(int A,int n)int i,j,t,f; /f=1时表示发生了交换操作for(f=1,i=n-1;i0&f;i-)for(f=0,j=0;jAj+1) /如果产生逆序f=1;t=Aj;Aj=Aj+1;Aj+1=t; /交换Aj与Aj+1的值4算法分析起泡排序算

16、法是稳定的。容易算出，该算法的时间复杂度为T(n)=O(n2)，空间复杂度为S(n)=O(1)。算法的基本操作是交换操作，如果待排序的数组基本有序，那么可以大量地减少排序过程中的交换操作。所以，起泡排序算法适用于序列为基本有序的场合。9.3.2快速排序法(Quick Sort)1算法思想快速排序算法的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小。接着对独立的每一组记录再分别进行排序和分割，直到每一组中都只有一个记录为止。2一趟快速排序的具体做法附设两个指针low,high,其初值分别指向首个记录和最后一个记录，另设关键字为Key的枢轴记录变量（

17、初始值为Low所指记录）。首先从High所指记录开始起向前搜索，找到第1个关键字小于Key的记录同时将该记录存储到Low所指记录中，然后从Low所指记录开始向后搜索，找到第1个关键字大于Key的记录存于High所指记录中，再重复以上步骤，直到Low=High为止。最后将Key中记录存储到Low所指记录中。3举例说明设原始记录序列为：38,13,27,76,65,49,49,97，其初始状态如图9.3所示。第1趟排序：27,13,(38),76,65,49,49,97第2趟排序：13,(27),(38),76,65,49,49,97第3趟排序：13,(27),(38),49,65,49,(76)

18、,97第4趟排序：13,(27),(38),(49),65,49,(76),97第5趟排序：13,(27),(38),(49),49,(65),(76),974快速排序的算法实现(1) 算法int Part(int* H,int low,int high)返回下标值i，使得在数组元素Hlow到Hhigh中,Hi前面的元素均小于等于Hi，Hi后面的元素均大于等于Hi。int Part(int* H,int low,int high)int key=Hlow;while(lowhigh)while(low=key) high-;Hlow=Hhigh;while(lowhigh&Hlow=key)

19、low+;Hhigh=Hlow;Hlow=key;return(low); /返回Hlow到Hhigh中的枢轴变量下标(2) 函数void Qsort(int* H,int low,int high)功能是，通过递归算法对数组H中从Hlow到Hhigh的元素进行快速排序。void Qsort(int* H,int low,int high) /对数组元素Hlow到Hhigh进行快速排序int p; /p为枢轴变量下标if(lowAj则i=j，最后，如果i!=0时执行A0与Ai的交换操作；第二趟，取下标值i=1,下标值j从2到n-1逐个由Ai与Aj进行比较，如果AiAj则i=j，最后，如果i!=

20、1时执行A1与Ai的交换操作；重复以上过程n-1次后，对数组An的排序过程结束。2举例说明设原始记录序列为：8、3、5、2、9、7、*5、4第1趟排序结果：(2),3,5,8,9,7,*5,4第2趟排序结果：(2,3),5,8,9,7,*5,4第3趟排序结果：(2,3,4),8,9,7,*5,5第4趟排序结果：(2,3,4,*5),9,7,8,5第5趟排序结果：(2,3,4,*5,5),7,8,9第6趟排序结果：(2,3,4,*5,5,7),8,9第7趟排序结果：(2,3,4,*5,5,7,8),93选择排序的算法实现void SelectSort(int A,int n)int i,j,k,

21、t;for(i=0;in-1;i+)for(k=i,j=i+1;jn;j+)if(Aj=(8)49;(3)65=(6)13和(7)27;自然满足；如图9.4(a)所示。第2步：(2)38=(4)97和(5)76不满足，执行操作：先38与97互换，再38与49互换。调整后到结果如图9.4(b)所示，其结果为：(1)49,(2)97,(3)65,(4)49,(5)76,(6)13,(7)27,(8)38第3步：(1)49=(2)97和(3)65不满足，先执行操作49与97互换，再49与76互换，调整结果如图9.4(c)所示。最终结果为：(1)97,(2)76,(3)65,(4)49,(5)49,(

22、6)13,(7)27,(8)38(2) 通过对序列的重复调整进行排序第1步：将(1),(8)互换，并将(1)到(7)的元素调整成为大顶堆，其结果如图9.5(a)所示。第1步调整的结果为：(1)76,(2)49,(3)65,(4)49,(5)38,(6)13,(7)27,97第2步：将(1),(7)互换，并将(1)到(6)的元素调整成为大顶堆，其结果如图9.5(b)所示。第2步调整的结果为：(1)65,(2)49,(3)27,(4)49,(5)38,(6)13,76,97第3步：将(1),(6)互换，并将(1)到(5)的元素调整成为大顶堆，其结果如图9.5(c)所示。第3步调整的结果为：(1)4

23、9,(2)49,(3)27,(4)13,(5)38,65,76,97第4步：将(1),(5)互换，并将(1)到(4)的元素调整成为大顶堆，其结果如图9.5(d)所示。第4步调整的结果如为：(1)49,(2)38,(3)27,(4)13,49,65,76,97依此类推，第5步为：(1)38,(2)13,(3)27,49,49,65,76,97；第6步为：(1)27,(2)13,38,49,49,65,76,97；第7步为：13,27,38,49,49,65,76,97。3堆排序的算法实现(1) 调整为大顶堆算法void HeapAdjust(int* H,int s,int m)的功能是，调整序

24、列H中元素，使序列中第s个到第m个元素成为大顶堆。void HeapAdjust(int* H,int s,int m)int j,t;t=Hs-1; j=s*2;while(j=m) /循环中s-1为双亲结点下标，j-1为孩子结点下标，t为要调整的值 if(jm&Hj-1=Hj-1)break; Hs-1=Hj-1;s=j; j=j*2;Hs-1=t;(2) 堆排序程序void HeapSort(int* H,int n)int i,t;for(i=n/2;i0;i-) /从最后一个分支结点开始通过循环调用HeapAdjust()构造初始堆HeapAdjust(H,i,n);cout0;i-

25、) /对初始堆H进行调整的排序过程t=H0;H0=Hi;Hi=t; HeapAdjust(H,1,i); /调整H中H0到Hi-1为堆4算法分析堆排序算法是不稳定的；堆排序在最坏的情况下，其时间复杂度也是T(n)=O(nlog2n)，相对于快速排序而言这是他的最大优点。由于实现堆排序时必须先构造初始堆，所以该算法在待排序数组的数据元素较多时其优势更为明显。9.5归并排序(Merging Sort)9.5.1归并的有关概念1n-路归并的概念将n个有序序列进行归并，生成一个新的有序序列的过程称为n-路归并。22-路归并排序的算法思想假设初始序列含有n个记录，可以将其看成是长度为1的n个有序子序列，

26、然后两两归并生成n/2个长度为2或1的有序子序列；下一步，再两两归并成n/4个长度为4或2或1的有序子序列；如此进行重复操作，直到最后得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序算法。3举例说明设原始记录序列为：38,13,49,76,65,27,49,97,33，其长度为n=9。先将其看成9个长度为1的有序序列为：(38),(13),(49),(76),(65),(27),(49),(97),(33)完成第1趟2路归并排序后得到9/2=5个有序序列，它们是：(13,38),(49,76),(27,65),(49,97),(33)完成第2趟2路归并排序后得到5/2=3个有序序

27、列，它们是：(13,38,49,76),(27,49,65,97),(33)完成第3趟2路归并排序后得到3/2=2个有序序列，它们是：(13,27,38,49,49,65,76,97),(33)完成第4趟归并排序后的结果为：(13,27,33,38,49,49,65,76,97)9.5.2 2-路归并排序的算法实现1两个有序序列的归并算法函数void Merge(int A,int s,int t,int n)的作用是将两个有序序列As,t, 和At+1,n归并到As,n。void Merge(int A,int s,int t,int n)int* C=new intn-s+1; /定义临时

28、存储空间Cint i,j,k;i=s,j=t+1,k=0;while(i=t&j=n)if(Ai=Aj) Ck+=Ai+;else Ck+=Aj+;while(i=t)Ck+=Ai+;while(j=n)Ck+=Aj+;for(k=0,i=s;i=n;i+)Ai=Ck+; /将C中的归并结果复制到A中deleteC;2归并排序算法的实现程序函数void MSort(int SR,int s,int t)的作用是，通过递归调用实现对数据元素SRs,t的排序过程。void MSort(int SR,int s,int t)int m=(s+t)/2;if(s=t)return;MSort(SR,s

29、,m);MSort(SR,m+1,t);Merge(SR,s,m,t);void MergeSort(int A,int n)MSort(A,0,n-1); 3算法分析归并排序算法是稳定的；该算法的时间复杂度是T(n)=O(nlog2n)，空间复杂度为S(n)=O(n)。归并排序算法的最大特点是该算法是稳定的；但是，该算法需要有存放n个元素大小的辅助空间。9.6基数排序(Radix Sort)算法9.6.1基数排序的有关概念1最低位基数优先(LSD)排序法假定序列中每个记录的关键字从高（左）到低（右）排列为：K1,K2,Kd,共有d个关键字。先按关键字Kd起对序列进行排序，然后再对序列按Kd-

30、1进行排序，依次重复，直到对K1进行排序后便成为一个有序序列。2举例说明设原始记录序列为：278,109,063,930,589,184,505,269,008,083(1) 从前往后按个位数排序(k3)：(930),(k3=1),(k3=2),(063,083),(184),(505),(k3=6),(k3=7),(278,008),(109,589,269)(2) 从前往后按十位排序(k2)：(505,008,109),(k2=1),(k2=2),(930),(k2=4),(k2=5),(063,269),(278),(083,184,589),(k2=9)(3) 从前往后按百位排序(k1

31、)：(008,063,083),(109,184),(269,278),(k1=3),(k1=4),(505,589),(k1=6),(k1=7),(k1=8),(930)排序结果为：8,63,83,109,184,269,278,505,589,9309.6.2基数排序法(LSD)的算法实现以下给出对n个整数的基数排序算法1函数Get(m,k)为取m的第k位数的值int Get(int m,int k)int i,n=m;for(i=1;ik;i+)n=n/10;n=n%10;return n;2按数组An中的第k位排序的操作void LSD(int A,int n,int k)int* p

32、10,i,j,s; /pi为关键字的值为i的所有元素int m10=0,e; /mi为pi中元素的最大下标。for(i=0;i10;i+)pi=new intn;for(i=0;in;i+) /根据数组An中第i个元素的第k位的值e将Ai分配到数组pe中；e=Get(Ai,k);peme+=Ai;for(i=0,j=0;j10;j+) /收集数组p0,p1,.,p9中的元素到数组An中；for(s=0;smj;s+)Ai+=pjs;deletepj;3低位优先(LSD)基数排序法的算法实现void RdSort(int A,int n)int m=A0,k,i;for(i=1;im)m=Ai;

33、 /求最大元素到变量m中k=1;while(m=m/10)k+; /求最大元素m的位数（宽度）kfor(i=1;i=k;i+)LSD(A,n,i); /按低位优先对数组A排序4算法分析基数排序法是稳定的，时间复杂度T(n)=O(d(n+rd),空间复杂度为S(n)=O(n)。其中d为关键字的个数，rd为关键字的取值个数。从基数排序算法的实现过程可知：该算法适用于n很大而且d比较小的情况。9.6.3调用各种排序算法进行排序的演示程序void main()int num;while(1)cout1-直接插入排序法,2-希尔排序法,3-冒泡排序法n;cout4-快速排序法,5-直接选择排序法,6-堆

34、排序法n;coutnum;switch(num)case 1:MainSort(InsertSort);break; case 2:MainSort(ShellSort);break;case 3:MainSort(BubbleSort);break;case 4:MainSort(QuickSort);break;case 5:MainSort(SelectSort);break;case 6:MainSort(HeapSort);break; case 7:MainSort(MergeSort);break;case 8:MainSort(RdSort);break;case 9:retu

35、rn;default: cout选择出错请重新选择:n;（运行过程略）9.7各种内部排序方法的比较内部排序在计算机程序设计中非常重要，本章中讨论的几种排序方法各有其优缺点，适用场合也不同。从排序方法的时间复杂度和空间复杂度以及排序方法的稳定性方面进行比较，归纳结果如表9.1所示。从表中数据可以得出如下结论：(1) 如果待排序记录的初始状态已经按关键字基本有序，则可选择起泡排序法或直接插入排序法。(2) 选择排序、起泡排序和插入排序仅适用于记录数n较小的情况。选择排序的时间性能与待排记录的初始状态无关，且该排序方法不稳定。插入排序在排序过程中无法知道部分连续位置上的最终元素。(3) 从平均时间复

36、杂度而言，快速排序法最佳。但快速排序在最坏的情况下（序列基本有序）时将蜕化为冒泡排序法，此时时间性能不如堆排序和归并排序。(4) 当记录数n较大时，归并排序比堆排序的速度快，且归并排序是稳定的而堆排序不稳定。但是，归并排序的辅助空间比堆排序多。(5) 基数排序可以在时间内完成对n个记录的排序。其中，d是指记录中所含逻辑关键字的最大个数，rd是指逻辑关键字的取值范围，即基数个数。基数排序法适用于字符串或整数等具有明显结构特征的关键字；如果n很大，d较小时，用基数排序较好。本章讨论的排序算法，都是在向量存储结构上实现的。当记录本身信息量很大时，为了避免大量时间用在移动数据上，可以利用链表作为存储结

37、构。插入排序和归并排序都容易在链表上实现，但是有的排序方法比如堆排序和快速排序方法就不易在链表上实现。9.8 习 题一、问答题1什么是内部排序？什么是排序方法的稳定性？2在本章介绍的内部排序方法中，稳定的排序方法有哪些？不稳定的排序方法有哪些？对于不稳定的排序方法试举例说明。3对于给定的一组记录的关键字：23,13,17,21,30,60,58,28试分别写出用下列排序方法对其进行排序时，每一趟排序后的结果：（1）直接插入排序； （2）希尔排序；（3）起泡排序； （4）直接选择排序；（5）快速排序； （6）堆排序；（7）归并排序。4对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于序列

38、中n个元素的初始排列顺序。（1）n=8时，在最好的情况下需要进行多少次比较？试说明理由。（2）给出n=8时的一个最好情况的初始排列实例。5试为下列各种情况选择合适的排序方法：（1）n=30，要求在最坏的情况下，排序速度最快；（2）n=30，要求排序速度最快，又要排序稳定。6判别以下序列是否为堆（包括大顶堆和小顶堆），如果不是，则把它调整成为堆。（1）（100,86,48,73,35,39,42,57,66,21）；（2）（12,70,33,65,24,56,48,92,86,33）；（3）（103,97,56,38,66,23,42,12,30,52,6,20）；（4）（5,56,20,3,2

39、3,40,38,29,61,5,76,28,100）。7一组待排序记录的关键字是：986,321,123,432,500,654,018,765,987,210按照LSD方法写出基数排序的过程和结果。8试构造对5个整数元素进行排序，最多只用7次比较的算法思想。9有n个不同的英文单词，它们的长度相等，均为m，如果n50,且m5,试问采取什么排序方法时间复杂度最佳？为什么？10如果想得到一个序列中第k个最小元素的部分排序序列，最好采用什么排序方法？为什么？如果有这样的一个序列：（57,40,38,11,13,34,48,57,25,6,19,9,7）得到其第4个最小元素之前的部分序列（6,7,9,

40、11），使用所选择的算法实现时，要执行多少次比较？二、填空题1在所学的排序方法中，关键字比较次数与记录的初始排列次序无关的是（ ）。2设有1000个无序元素，希望用最快的速度挑选出其中的前10个最大的元素，最好选用（ ）排序法。3在待排序的元素序列基本有序的情况下，效率最高的排序方法是（ ）。4一组记录的关键字为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆是（ ）。5一组记录的关键字值是（46,82,40,52,67,31,21,73），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。6排序方法中，从未排序序列中依次取出元素，与已排序序列（初始为空

41、）中的元素进行比较，将其插入已排序序列的正确位置上的方法，称为（ ）。7排序方法中，从未排序序列中依次取出元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ ）。8用某种排序方法，对元素序列（25,84,21,47,15,27,68,35,20）进行排序，每一趟排序后元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则采用的排序方法是（ ）。9快速排序方法在（ ）情况下最不利于发挥其长处。10在插入排序、选择排序、快速排序和归并排序中（ ）方法要求其内存量最大。11在插入排序、选择排序、快速排序和归并排序中，平均查找时间最短的是（ ）。12使用直接插入排序法对一组记录（54,38,96,23,15,72,60,54,83）进行排序，当把第7个记录60插入到有序表时，为寻找插入位置需要比较（ ）次