大学数据结构课件--第10章内部排序

1、1 10.1 10.1 概述概述 10.2 10.2 插入排序插入排序 10.3 10.3 交换排序交换排序 10.4 10.4 选择排序选择排序 10.5 10.5 归并排序归并排序 10.6 10.6 基数排序基数排序（直接插入排序、希尔排序）（直接插入排序、希尔排序）（起泡排序、快速排序）（起泡排序、快速排序）（直接选择排序、堆排序）（直接选择排序、堆排序）第第10章章 内部排序内部排序21. 什么是排序？什么是排序？ 将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。2. 排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按关键字

2、排序按关键字排序3. .排序算法的好坏如何衡量？排序算法的好坏如何衡量？ 时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数） 空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小 稳定性稳定性若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B 的先后次序保持不变，则称此排序算法是稳定的。的先后次序保持不变，则称此排序算法是稳定的。 便于查找！便于查找！10.1 概述概述3若待排序记录都在内存中，称为内部排序；若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。

3、若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：注：外部排序时，要将数据分批调入内存来排序，中间结果还要及外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。时放入外存，显然外部排序要复杂得多。 5.待排序记录在内存中怎样存储和处理？大多数排序算法都有两个基本的操作：大多数排序算法都有两个基本的操作：（1）比较两个关键字的大小）比较两个关键字的大小（2）将记录从一个位置移动到另一个位置）将记录从一个位置移动到另一个位置（1）顺序存储顺序存储 （2）静态链表）静态链表 （3）地址）地址4. 什么叫内部排序？什么叫外部排序？10.1 概述概述4注：

4、注：大多数排序算法都是针对顺序表结构的大多数排序算法都是针对顺序表结构的( (便于直接移动元素便于直接移动元素) )Typedef struct /定义每个记录（数据元素）的结构定义每个记录（数据元素）的结构 KeyType key ; /关键字关键字 InfoType otherinfo; /其它数据项其它数据项RecordType ;Typedef struct /定义顺序表的结构定义顺序表的结构 RecordType r MAXSIZE +1 ; /存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区 int length ; /顺序表的长度顺序表的长度Sq

5、List ;# define MAXSIZE 20 /设记录不超过设记录不超过2020个个typedef int KeyType ; /设关键字为整型量（设关键字为整型量（intint型）型）6. 顺序存储（顺序表）的抽象数据类型10.1 概述概述5插入排序的基本思想是：插入排序的基本思想是：插入排序有多种具体实现算法：插入排序有多种具体实现算法： （1）直接插入排序）直接插入排序 （2） 折半插入排序折半插入排序 （3） 表插入排序表插入排序 （4）希尔排序）希尔排序 每步将一个待排序的对象，每步将一个待排序的对象，按其关键码大小，按其关键码大小，插入到前面插入到前面已经排好序的一组对象已经

6、排好序的一组对象的适当位置上的适当位置上，直到对象全部插入为止。，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。10.2 插入排序插入排序6直接插入排序是直接插入排序是最简单的排序方法新元素插入到哪里？新元素插入到哪里？在已形成的在已形成的有序表中有序表中线性查找线性查找，并在适当位置插入，并在适当位置插入，把原来位置上的元素向后把原来位置上的元素向后顺移顺移。10.2.1 直接插入排序直接插入排序7例例1 1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。 【13】

7、, 6, 3, 31, 9, 27, 5, 11第一趟直接插入排序第一趟直接插入排序【6, 13】, 3, 31, 9, 27, 5, 11第二趟直接插入排序第二趟直接插入排序【3, 6, 13】, 31, 9, 27, 5, 11第三趟直接插入排序第三趟直接插入排序【3, 6, 13，31】, 9, 27, 5, 11第四趟直接插入排序第四趟直接插入排序【3, 6, 9, 13，31】, 27, 5, 11第五趟直接插入排序第五趟直接插入排序【3, 6, 9, 13，27, 31】, 5, 11第六趟直接插入排序第六趟直接插入排序【3, 5, 6, 9, 13，27, 31】, 11第七趟直

8、接插入排序第七趟直接插入排序【3, 5, 6, 9, 11，13，27, 31】 10.2.1 直接插入排序直接插入排序8例例2 2：关键字序列关键字序列T= （21，25，49，25*，16，08），），请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。0 1 2 3 4 5 6254925*1608解：解：假设该序列已存入一维数组假设该序列已存入一维数组V7V7中，将中，将V0V0作为缓冲或暂存单元作为缓冲或暂存单元（TempTemp）。则程序执行过程为：）。则程序执行过程为：初态：初态：时间效率：时间效率： 因为在最坏情况下，所有元素的比较次数总和为因为在最坏情况下，所

9、有元素的比较次数总和为（0 01 1n-1)O(nn-1)O(n2 2) )。其他情况下还要加上移动元素。其他情况下还要加上移动元素的次数。的次数。 空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为2525* *排序后仍然在排序后仍然在2525的后面。的后面。9void Insertsort() int i,j; for(i=2;i=N;i+) p0=pi; j=i-1; while(p0 pj) pj+1=pj; j-; pj+1=p0; i ij jj jj j直接插入排序算法直接插入排序算法10基本思想基本思想 先将整个待排记录序列分

10、割成若干子序列先将整个待排记录序列分割成若干子序列, ,分别进行直分别进行直接插入排序，待整个序列中的记录接插入排序，待整个序列中的记录“基本有序基本有序”时，再对时，再对全体记录进行一次直接插入排序。全体记录进行一次直接插入排序。技巧技巧 子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割”，而是将相隔某，而是将相隔某个增量个增量dkdk的记录组成一个子序列的记录组成一个子序列, ,让增量让增量dkdk逐趟缩短（例如逐趟缩短（例如依次取依次取5,3,15,3,1），直到），直到dkdk1 1为止。为止。10.2.3 希尔（希尔（shell）排序）排序（又称缩小增量排序）（又称缩小

11、增量排序）1138例：关键字序列例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写），请写出希尔排序的具体实现过程。出希尔排序的具体实现过程。0123456789104938659776132749*5504初态：初态：第第1趟趟 (dk=5)第第2趟趟 (dk=3)第第3趟趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 4

12、913382749* 6555970476算法分析：算法分析：开始时开始时dk 的值较大，子序列中的对象较少，排序速度较快；的值较大，子序列中的对象较少，排序速度较快； 随着排序进展，随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，值逐渐变小，子序列中对象个数逐渐变多， 由于前面工作的基础，大多数对象已基本有序，所以排序速度由于前面工作的基础，大多数对象已基本有序，所以排序速度 仍然很快。仍然很快。12 两两比较待排序记录的关键码，两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排

13、好序为止。则交换之，直到所有记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有： （1）冒泡排序）冒泡排序 （2）快速排序）快速排序交换排序的基本思想是：交换排序的基本思想是：10.3 交换排序交换排序13基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大” （或（或“前大后小前大后小”）规则交换。）规则交换。例：关键字序列 T=(21，25，49，25*，16，08），请写出 冒泡排序的具体实现过程。21，25，49， 25*，16，0821，25， 25，49， 25* ,49， 16， 49， 08 ， 49第第1趟冒泡排序结果趟冒泡

14、排序结果21，25， 25* , 16， 08 ， 4910.3.1 冒泡排序冒泡排序14void bsort (int a , int n) int temp,i,j; int flag; /交换标志交换标志 for(j=1;j=n-1;j+) /最多做最多做n-1趟排序趟排序 flag=0; /本趟排序开始前，交换标志应为本趟排序开始前，交换标志应为0 for(i=1;iai+1) /交换记录交换记录 temp=ai; ai=ai+1; ai+1=temp; flag=1; /发生了交换，故将交换标志置为真发生了交换，故将交换标志置为真 if(flag= =0) break; /本趟排序未

15、发生交换，提前终止算法本趟排序未发生交换，提前终止算法 冒泡排序的算法冒泡排序的算法15 从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。基本思想：基本思想：例1：关键字序列 T=(21，25，49，25*，16，08），请写出 快速排序的算法步骤。(设以首元素为枢轴中心)10.3.2 快速排序快速排序21， 25， 49， 25*，16， 08i ij j08， 25， 49， 25*，16， i ij j08， ， 49，

16、 25*，16， 25 j ji i08，16 ， 49， 25*， ， 25 j ji i08，16 ， ， 25*， 49 ， 25 j ji i08，16 ， ，25*， 49， 25 j ji i0821,0821,2521,所以交换，所以交换，j-j-1621,1621,4921,所以交换，所以交换，j-j-第第1趟快速排序结果趟快速排序结果08，16，21，25*， 49， 25第第1趟快速排序结果趟快速排序结果 08，16，21，25*， 49， 25，分别对分别对 08，16 和和 25*，49， 25进行快速排序进行快速排序对对08，16 进行快速排序进行快速排序 08， 1

17、6i ij j08， 16i i j j0816,0816,不需要交换，不需要交换，j-j- 08，16 快速排序结果快速排序结果08，16对对25*，49， 25进行快速排序进行快速排序 25*， 49，25i ij j25*， 49，25i ij j2525* *=25,=25,不需要交换，不需要交换，j-j- 25*，49，25 快速排序结果快速排序结果25*，49，2525*， 49，25i ij j2525* *49,49,不需要交换，不需要交换，j-j-第第2趟快速排序结果趟快速排序结果 08，16，21，25*， 49，2518pivotkey=pivotkey=ri.keyri

18、.key; ; /取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(i j)while(i j) /从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(i=pivotkey ) while(i=pivotkey ) ri=rj; ri=rj; /将比支点小的记录交换到低端；将比支点小的记录交换到低端；while(ij & ri.key=pivotkey) while(ij & ri.key=pivotkey) rj=ri; rj=ri; /将比支点大的记录交换到高端；将比支点大的记录交换到高端； ri=r0; ri=r0; /支

19、点记录到位；支点记录到位；return i; return i; /返回支点记录所在位置。返回支点记录所在位置。 /int int (SqList &L,int i,int(SqList &L,int i,int j j) ) /一趟快排一趟快排 r0=ri; r0=ri; /以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元一趟快速排序算法（针对一个子表的操作）每一趟的子表的形成是采用从两头向中间交替式逼近法；每一趟的子表的形成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都相似，主程序可采用递归算法。由于每趟中对各子表的操作都相似，主

20、程序可采用递归算法。快速排序算法快速排序算法19void QSort ( SqList &L, int i, int j ) if ( i 1/对顺序表对顺序表L中的子序列中的子序列r ij 作快速排序作快速排序/一趟快排，将一趟快排，将r 一分为二一分为二/在左子区间进行递归快排，直到长度为在左子区间进行递归快排，直到长度为1/在右子区间进行递归快排，直到长度为在右子区间进行递归快排，直到长度为1/QSort快速排序算法快速排序算法20选择排序有多种具体实现算法选择排序有多种具体实现算法 （1）简单选择排序）简单选择排序 （2）堆排序）堆排序每一趟在后面n-i个待排记录中选取关键字最

21、小的记录作为有序序列中的第i个记录。10.4 选择排序选择排序21思路简单：思路简单：每经过一趟比较就找出一个最小值，与待每经过一趟比较就找出一个最小值，与待 排序列最前面的位置互换即可。排序列最前面的位置互换即可。首先，在n个记录中选择最小者放到r1位置；然后，从剩余的n-1个记录中选择最小者放到r2位置；如此进行下去，直到全部有序为止。10.4.1 简单选择排序简单选择排序22例：关键字序列T= （21，25，49，25*，16，08），请给出 简单选择排序的具体实现过程。原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25

22、，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49最小值最小值 0808 与与r1r1交换位置交换位置10.4.1 简单选择排序简单选择排序23SELECTSORT( ) int i,j,k; for (i=1;in;i+) k=i; for (j=i+1;j=n;j+) if (p j p k ) k=j; if (k!=i) temp=p i ; p i =p k ; p k =temp; /在在ririnn中选择中选择keykey最小的记录最小的记录/与第与第i

23、 i个记录交换个记录交换简单选择排序的算法简单选择排序的算法241. 1. 什么是堆？什么是堆？堆的定义：堆的定义：设有设有n个元素的序列个元素的序列 k1，k2，kn，当且仅，当且仅当满足下述关系之一时，称之为堆。当满足下述关系之一时，称之为堆。 ki k2iki k2i+1ki k2iki k2i+1或者或者i=1, 2, n/2解释：解释：如果让满足以上条件的元素序列如果让满足以上条件的元素序列 （k1，k2，kn） 顺次排成一棵顺次排成一棵完全二叉树完全二叉树，则此树的特点是：，则此树的特点是： 树中所有根结点的值均大于（或小于）其左右孩子，树中所有根结点的值均大于（或小于）其左右孩子

24、， 此树的此树的根结点（即堆顶）根结点（即堆顶）必最大（或最小）。必最大（或最小）。2. 2. 怎样建堆？怎样建堆？3. 3. 怎样堆排序？怎样堆排序？10.4.2 堆排序堆排序25234561（大根堆）（大根堆）2345617例：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？（小根堆）（小根堆）（小顶堆）（小顶堆） （最小堆）（最小堆）（大顶堆）（大顶堆）（最大堆）（最大堆）10.4.2 堆排序堆排序26步骤：步骤：从从最后一个最后一个非终端结点非终端结点开始开始往前往前逐步调整，让每个

25、逐步调整，让每个 双亲大于（或小于）子女，直到根结点为止。双亲大于（或小于）子女，直到根结点为止。123456例：例：关键字序列关键字序列T= (21，25，49，25*，16，08），请建大根堆。），请建大根堆。解：为便于理解，先将原始序列画成完全二叉树的形式为便于理解，先将原始序列画成完全二叉树的形式完全二叉树的最后一个非终端完全二叉树的最后一个非终端结点编号必为结点编号必为 n/2n/2 ！注：注：终端结点（即叶子）没有任何子女，无需单独调整。终端结点（即叶子）没有任何子女，无需单独调整。 49大于大于08，不必调整；，不必调整； 25大于大于25*和和16，也不必调整；，也不必调整；

26、21小于小于25和和49，要调整！，要调整！而且而且21还应当向下比较！还应当向下比较！2. 怎样建堆？怎样建堆？27关键：将堆的当前顶点输出后，如何将剩余序列 重新调整为堆？方法：将当前顶点与堆尾记录交换，然后仿建堆 动作，从上至下新调整，如此反复直至排 序结束。3. 怎样进行堆排序？怎样进行堆排序？28删除49123456136542例：对刚才建好的大根堆进行排序例：对刚才建好的大根堆进行排序29删除2512345613654212345630归并排序的基本思想是：归并排序的基本思想是：将两个（或以上）的有序表 组成新的有序表。更实际的意义：更实际的意义：可以把一个长度为可以把一个长度为n

27、 的无序序列看成是的无序序列看成是 n 个个长度为长度为 1 的有序子序列的有序子序列 ，首先做两两归并，得到，首先做两两归并，得到 n / 2 个个长度为长度为 2 的子序列的子序列 ；再做两两归并，；再做两两归并，如此重复，直到最，如此重复，直到最后得到一个长度为后得到一个长度为 n 的有序序列。的有序序列。10.5 归并排序归并排序31例：关键字序列关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。），请给出归并排序的具体实现过程。32要讨论的问题：要讨论的问题：1.什么是“多关键字”排序？实现方法？2.单逻辑关键字怎样

28、“按位值”排序？基数排序的基本思想是：基数排序的基本思想是：借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。10.6 基数排序基数排序33例例1：对一副扑克牌该如何排序？：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为：若规定花色和面值的顺序关系为： 花色：花色： 面值：面值：2 3 4 5 6 7 8 9 10 J Q K A多关键字排序的实现方法通常有两种：最高位优先法最高位优先法MSD (Most Significant Digit first)最低位优先法最低位优先法LSD (Least Significant Digit first)1.什么是什

29、么是“多关键字多关键字”排序？实现方法？排序？实现方法？34例：对一副扑克牌该如何排序？例：对一副扑克牌该如何排序？答答：若规定花色为第一关键字（高位），面值为第二关键字（低位），若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用则使用MSD和和LSD方法都可以达到排序目的。方法都可以达到排序目的。MSD方法的思路：方法的思路：先设立先设立4个花色个花色“箱箱”，将全部牌按花色分别归入，将全部牌按花色分别归入4个箱内（每个箱中有个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行排序。张牌）；然后对每个箱中的牌按面值进行排序。LSD方法的思路：方法的思路：先按面值分成先按面

30、值分成13堆（每堆堆（每堆4张牌），然后对每堆中的张牌），然后对每堆中的牌按花色进行排序。牌按花色进行排序。1.什么是什么是“多关键字多关键字”排序？实现方法？排序？实现方法？35设设n n 个记录的序列为：个记录的序列为： V V0 0, , V V1 1, , , , V Vn n-1-1 ，可以把每个记录，可以把每个记录V Vi i 的的单关键码单关键码 K Ki i 看成是一个看成是一个d d元组元组（K Ki i1 1, , K Ki i2 2, , , , K Ki id d），则其中，则其中的每一个分量的每一个分量K Ki ij j ( 1( 1 j j d d ) ) 也可看成

31、是一个关键字。也可看成是一个关键字。4注注1 1： K Ki i1 1最高位，最高位，K Ki id d最低位；最低位；K Ki i共有共有d d位，可看成位，可看成d d元组；元组；注注2： 每个分量每个分量K Ki ij j (1 j d ) 有有radix种取值，则称种取值，则称radix为基数。为基数。26(9, 8, 4)(0, 1, , 9)（a, b, , z）(d, i, a, n)310例例1：关键码关键码984可以看成是可以看成是 元组；基数元组；基数radix 为为 。例例2：关键码关键码dian可以看成是可以看成是 元组；基数元组；基数radix 为为 。思路：思路：2

32、.单逻辑关键字怎样单逻辑关键字怎样“按位值按位值”排序？排序？36例：例：初始关键字序列初始关键字序列T=（32, 13, 27, 32*, 19，33），），请分别用请分别用MSD和和LSD进行排序。进行排序。法法1（MSD）：）：原始序列：原始序列：32, 19, 27, 32*, 13， 33 先按高位先按高位K Ki i1 1 排序：排序：（19, 13）, 27, （32, 32*，33） 再按低位再按低位K Ki i2 2 排序排序 ： 13, 19 ， 27, 32, 32*, 33法法2（LSD）：）： 原始序列：原始序列： 32, 13, 27, 32*, 19 ，33 先按

33、低位先按低位K Ki i2 2排序：排序： 32, 32*, 13, 33, 27, 19 再按高位再按高位K Ki i1 1排序：排序： 13, 19 , 27, 32, 32*, 33这种这种LSD排序方法称为：排序方法称为：基数排序基数排序用链队列来实现基数排序用链队列来实现基数排序链式基数排序链式基数排序2.单逻辑关键字怎样单逻辑关键字怎样“按位值按位值”排序？排序？37例:请实现以下关键字序列的链式基数排序：请实现以下关键字序列的链式基数排序： T=T=（614614，738738，921921，485485，637637， 101101，215215，530530，790790，3

34、06306）e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9r0f e eifi+1 530790921101614485215306637738r038e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738eifi+1 530790921101614485215306637738r0r0

35、第一趟收集的结果第一趟收集的结果39530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9eifi+1 530790921101614485215306637738r0r0第二趟收集的结果第二趟收集的结果40简单排序简单排序 O(n)O(n2) O(n2) O(1） 稳定稳定 快速排序快速排序O(nlgn )O(nlgn) O(n2) O(lgn) 不稳定不稳定 堆排序堆排序 O(nlgn )O(nlgn ) O(

36、nlgn) O(1）不稳定不稳定 归并排序归并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n）稳定稳定基数排序基数排序O(d(n+rd) O(d(n+rd) O(d(n+rd) O(rd)稳定稳定 简单选择简单选择 O(n2) O(n2) O(n2) O(1） 不稳定不稳定 直接插入直接插入 O(n) O(n2) O(n2) O(1）稳定稳定 折半插入折半插入O(nlgn )O(nlgn )O(nlgn )O(1）稳定稳定冒泡冒泡 O(n) O(n2) O(n2) O(1）稳定稳定 各种内部排序方法的比较各种内部排序方法的比较411. 以关键字序列（以关键字序列（256，30

37、1，751，129，937，863，742，694，076，438）为例，写出执行直接插入排序的）为例，写出执行直接插入排序的各趟各趟排序过程。排序过程。原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，43843812912

38、9，256256，301301，751751，937937，863863，742742，694694，076076，438438129129，256256，301301，751751，937937，863863，742742，694694，076076，438438129129，256256，301301，751751，863863，937937，742742，694694，076076，438438129129，256256，301301，742742，751751，863863，937937，694694，076076，438438129129，256256，301301，694694，7

39、42742，751751，863863，937937，076076，438438076076，129129，256256，301301，694694，742742，751751，863863，937937，438438076076，129129，256256，301301，438438，694694，742742，751751，863863，937937第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟 练习练习42Q,P,R,Y,S ,XC,M,F,H,A,D,P,Q,R,2. 欲将序列（欲将序列（Q, H, C, Y, P, A, M, S, R,

40、D, F, X）中的关键码按字）中的关键码按字母升序重排，则初始步长为母升序重排，则初始步长为4的希尔排序第一趟的结果是？的希尔排序第一趟的结果是？答：答：原始序列：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shellshell一趟后：一趟后：A,D,H,C,F,M,S,X ,Y第一趟希尔排序结果：第一趟希尔排序结果：P A C S Q D F X R H M Y练习练习433 3、设文件有、设文件有1010个记录，其关键字值分别个记录，其关键字值分别为为:37,23,7,79,29,43,73,19,31,61,:37,23,7,79,29,43,73

41、,19,31,61,试给出冒泡排序法按非递减的次试给出冒泡排序法按非递减的次序进行排序过程中的每一趟结果序列。序进行排序过程中的每一趟结果序列。 4 4、有一组键值、有一组键值2525，8484，2121，4747，1515，2727，6868，3535，2424，采用快速排序方，采用快速排序方法由小到大进行排序，请写出第一趟排序过程中键值的移动情况。法由小到大进行排序，请写出第一趟排序过程中键值的移动情况。 5 5、已知有十个待排序的记录，其关键字分别为：、已知有十个待排序的记录，其关键字分别为：256256，301301，751751，129129，937,863937,863，742742，694694，076076，438438请用快速排序的方法将它们从小到大请用快速排序的方法将它们从小到大排列。排列。6 6、设待排序的记录共、设待排序的记录共7 7个，排序码分别为个，排序码分别为8 8，3 3，2 2，5 5，9 9，1 1，6 6。 (1) (1) 写出直接插入排序的全过程，要求按递减顺序排序。写出直接插入排序的全过程，要求按递减顺序排序。 (2) (2) 写出直接选择排序的全过程，要求按递减顺序排序。写出直接选择排序的全过程，要求按递减顺序排序。练习练习447 7、设文件有、设文件有1212个记录个记录, ,其关键