数据结构之树和图算法精品文稿.ppt

《数据结构之树和图算法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构之树和图算法精品文稿.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9章 排序数据结构之树和图算法第1页，本讲稿共70页假设假设 Ki=Kj，且排序前序列中，且排序前序列中 Ri 领先于领先于 Rj；若在排序后的序列中若在排序后的序列中 Ri 仍领先于仍领先于 Rj，则称排序方法是，则称排序方法是稳定稳定的的。若在排序后的序列中若在排序后的序列中 Rj 仍领先于仍领先于 Ri，则称排序方法是，则称排序方法是不稳不稳定的定的。例，序列例，序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15稳定的稳定的若排序后得若排序后得 3 6 8 8 9 15不稳定的不稳定的稳定排序与不稳定排序第2页，本讲稿共70页内部排序内部排序:指的是待排序记录

2、存放在计算机指的是待排序记录存放在计算机随机存储器随机存储器中进行中进行的排序过程。的排序过程。外部排序外部排序:指的是待排序记录的数量很大，以致内存一次不指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对能容纳全部记录，在排序过程中尚需对外存外存进行访问的排序进行访问的排序过程。过程。内部排序与外部排序第3页，本讲稿共70页排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析

3、一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。第4页，本讲稿共70页按照排序过程中所依据的原则的不同可以分类为按照排序过程中所依据的原则的不同可以分类为:插入排序插入排序 交换排序交换排序(快速排序快速排序)选择排序选择排序 归并排序归并排序 基数排序基数排序 二叉排序树排序二叉排序树排序内部排序第5页，本讲稿共70页思想思想:利用有序表的插入操作进行排序利用有序表的插入操作进行排序有序表的插入有序表的插入:将一个记录插入到已排好序的有序表中，从而得将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。到一个新的有序表。例，序列例，序列 13 27

4、38 65 76 97 插入插入 4913 27 38 49 65 76 97插入排序直接插入排序第6页，本讲稿共70页例，序列例，序列 49 38 65 97 76 13 27 初始，初始，S=49 ；38 49 初始，令第初始，令第 1 个元素作为初始有序表；个元素作为初始有序表；依次插入第依次插入第 2,3,k 个元素构造新的有序表；个元素构造新的有序表；直至最后一个元素；直至最后一个元素；38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用直接插入排序算法主要应用比

5、较比较和和移动移动两种操作。两种操作。直接插入排序算法描述第7页，本讲稿共70页void insertsort(ElemType R,int n)/待排序元素用一个数组R表示，数组有n个元素 for(int i=1;i=0)&(tempRj)Rj+1=Rj;j-;/顺序比较和移动 Rj+1=temp;第8页，本讲稿共70页直接插入排序的效率分析直接插入排序的效率分析从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。Cmin=n-1 M min=2

6、（n-1）Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4 M max=（n2+7n-8）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。第9页，本讲稿共70页由于直接插入排序算法利用了有序表的插入操作，故由于直接插入排序算法利用了有序表的插入操作，故顺序查顺序查找找操作可以替换为操作可以替换为折半查找折半查找操作。操作。例，序列例，序列 49 38 65 97 76 13 27 设已形成有序表设已形成有序表 38 49 65 97 76 插入元素插入元素 13折半插入排

7、序第10页，本讲稿共70页算法:void BinaryInsertSort(ElemType R,int n)for(int i=1;in;i+)/共进行n-1次插入 int left=0,right=i-1;ElemType temp=Ri;while(left=right)int middle=(left+right)/2;/取中点 if(temp=left;j-)Rj+1=Rj;/元素后移空出插入位 Rleft=temp;第11页，本讲稿共70页折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况

8、坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。第12页，本讲稿共70页分析直接插入排序分析直接插入排序1.若待排序记录序列按关键字若待排序记录序列按关键字基本有序基本有序，则排序效率可大，则排序效率可大大提高；大提高；2.待排序记录总数越少，排序效率越高；待排序记录总数越少，排序效率越高；希尔(shell)排序第13页，本讲稿共70页思想:先将待排序记录序列分割成为若干子序列分别进行直接插入排序；先将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进

9、行一次直接插入排序。待整个序列中的记录基本有序后，再全体进行一次直接插入排序。例，序列例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76第14页，本讲稿共70页第二趟排序第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764 27 49 6519 48 97第三趟排序第三趟排序4 13 19 27 38 48 49 55 65 76 97第15页，本讲稿

10、共70页希尔排序的算法希尔排序的算法希尔排序的算法希尔排序的算法template void ShellSort(T Vector,int arrSize )T temp;int gap=arrSize/2;/gap是子序列间隔 while(gap!=0)/循环,直到gap为零 for(int i=gap;i=gap;j-=gap)if(temp Vectorj-gap)Vectorj=Vectorj-gap;else break;Vectorj=temp;gap=(int)(gap/2);第16页，本讲稿共70页希尔排序效率分析希尔排序的时间复杂性在O（nlog2n）和O（n2）之间，大致为O

11、（n1.3）。第17页，本讲稿共70页思想思想:通过不断比较相邻元素大小，进行交换来实现排序。通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；首先将第一个元素与第二个元素比较大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；.直至比较第直至比较第 n-1 个元素与第个元素与第 n 个元素的大小，若为逆序，则交换；个元素的大小，若为逆序，则交换；第一趟排序第一趟排序:结果结果:关键字最大关键字最大的记录被交换至的记录被交换至最后最后一个元素位置上。一个元素位

12、置上。交换排序冒泡排序第18页，本讲稿共70页例，序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初初始始第第一一趟趟排排序序后后最大值最大值13 4927 49次大值次大值第第二二趟趟排排序序后后38 13 2713 2713 38 27 38第第三三趟趟排排序序后后第第四四趟趟排排序序后后第19页，本讲稿共70页冒泡排序的算法实现冒泡排序的算法实现。void Bubblesort(ElemType R,int n)int flag=1;/当flag为0则停止排序 for (int i=1;i=i;j-)if(RjRj-1)

13、/发生逆序 ElemType t=Rj;Rj=Rj-1;Rj-1=t;flag=1;/交换，并标记发生了交换 if(flag=0)return;第20页，本讲稿共70页冒泡排序的效率分析冒泡排序的效率分析从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。第21页，本讲稿共70页

14、冒泡排序的一种改进算法。冒泡排序的一种改进算法。思想思想:以以首记录首记录作为作为轴记录轴记录，从前、后双向扫描序列，通过交换，实，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。当的位置。(小值记录在前、大值记录在后小值记录在前、大值记录在后)轴记录轴记录将原序列分割成两部分，依次对前后两部分重新设定轴将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。记录，继而分别再进行快速排序。直至整个序列有序。直至整个序列有序。交换排序快速排序第22页，本讲稿共70页快排序

15、（Quick Sort)快速排序实例n快排序算法思想第23页，本讲稿共70页快排序（Quick Sort)|快排序-分割过程z快排序是一个分治算法（也是第一个）z快排序的关键过程是每次递归的分割过程z分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边z分割算法：用临时变量对轴备份取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high移动两个指针l首先从high所指的位置向左搜索，找到第一个小于轴的元素,把这个元素放在low的位置l再从low开始向右，找到第一个大于轴的元素，把它放在high的位置第2

16、4页，本讲稿共70页快排序（Quick Sort)|快排序-分割过程z分割算法：重复上述过程，直到low=high，把轴放在low所指的位置这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边第25页，本讲稿共70页快排序（Quick Sort)|快排序-分割过程38 65 97 76 13 27 4938 65 97 76 13 27 4949lowlowhighhighpivot=49 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7highhigh38 65 97 76 13 4938 65 97 76 13 4927lowlow2727 38 97 76 13 49

17、38 97 76 13 4965highhigh27 38 97 76 65 4913lowlow27 38 13 76 65 65 499797highhigh49第26页，本讲稿共70页快排序（Quick Sort)|快排序-分割过程int Partition(T Array,int low,int high)T pivot=Arraylow;/while(low high)/在作为快排序的子程序时不用 while(low=pivot)high-;Arraylow=Arrayhigh;while(low high&Arraylow=pivot)low+;Arrayhigh=Arraylow

18、;/在作为快排序的子程序时不用 Arraylow=pivot;return low;第27页，本讲稿共70页快排序（Quick Sort)|快排序-算法z快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1 0 1 2 3 4 5 6 70 1 2 3 4 5 6 749 38 65 97 76 13 27 49 76 97 65 4927 38 1349494913133827 49 65 49 6597767613 17 38 49 76 9749 65第28页，本讲稿共70页快排序（Quick Sort)|快排序-算法void QuickSort(T Array,i

19、nt low,int high)int PivotLocation;if(low high)PivotLocation=Partition(Array,low,high);QuickSort(Array,low,PivotLocation-1);QuickSort(Array,PivotLocation+1,high);第29页，本讲稿共70页3快速排序的效率分析快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1，所以总的比较次数不会超过(n+1)log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而

20、且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1in）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。第30页，本讲稿共70页思想思想:每一趟都选出一个最大或最小的元素，并放在合适当每一趟都选出一个最大或最小的元素，

21、并放在合适当的位置。的位置。简单选择排序简单选择排序 树形选择排序树形选择排序 堆排序堆排序选择排序第31页，本讲稿共70页思想思想:第第 1 趟选择趟选择:从从 1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 1 个个记录交换。记录交换。第第 2 趟选择趟选择:从从 2n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 2 个个记录交换。记录交换。第第n-1趟选择趟选择:从从 n-1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 n-1 个记录交换。个记录交换。.简单选择排序第32页，本讲稿共70页例，序

22、列 49 38 97 65 76第第 1 趟选择趟选择:min38 49 97 65 76第第 2 趟选择趟选择:min38 49 97 65 76第第 3 趟选择趟选择:min38 49 65 97 76第第 4 趟选择趟选择:min38 49 65 76 97第33页，本讲稿共70页直接选择排序的算法直接选择排序的算法直接选择排序的算法直接选择排序的算法template void SelectSort(T Vector,int CurrentSize)for(int i=0;i CurrentSize-1;i+)int k=i;/选择具有最小排序码的对象 for(int j=i+1;j C

23、urrentSize;j+)if(Vectorj Vectork)k=j;/当前具最小排序码的对象 if(k!=i)/对换到第 i 个位置 Swap(Vectori,Vectork);第34页，本讲稿共70页选择排序的主要操作是进行关键字间的比较。在在 n 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-1 次比较次比较。在剩余的在剩余的 n-1 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-2 次比次比较较？如果能利用前如果能利用前 n-1 次比较所得信息，可以减少后面选择的比较次次比较所得信息，可以减少后面选择的比较次数。数。体育比赛中的锦标赛体育比赛

24、中的锦标赛:第35页，本讲稿共70页例，8 名运动员要决出 冠、亚、季军。按简单选择排序需要比赛按简单选择排序需要比赛 7+6+5=18 场。场。若能够利用以前的比赛结果，比赛场次实际可以减少为若能够利用以前的比赛结果，比赛场次实际可以减少为 11 场。场。前提前提:若若 甲甲 胜胜 乙乙，乙，乙 胜胜 丙丙，则，则 甲甲 必能胜必能胜 丙丙。ZhaoChaLiuBaoDiaoYangXue WangBaoBaoDiaoChaBaoDiaoWang冠军冠军第36页，本讲稿共70页如何求 亚军？ZhaoChaLiuDiaoYangXue WangChaDiaoCha亚军亚军可以利用前面的比赛结果

25、！可以利用前面的比赛结果！ChaLiuDiaoWang第37页，本讲稿共70页如何求 季军？ZhaoLiuDiaoYangXue WangLiuDiaoDiao季军季军同样可以利用前面的比赛结果！同样可以利用前面的比赛结果！LiuDiaoWangZhao第38页，本讲稿共70页又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟选择第一趟选择133813493865977613275038651327最小值最小值树形选择排序第39页，本讲稿共70页第二趟选择27

26、38274938659776275038657627次小值次小值第三趟选择第三趟选择38385049386597765038657650次次小值次次小值493865977613275049386597762750缺点:需要大量辅助存储空间第40页，本讲稿共70页堆堆:一棵完全二叉树，任一个非终端结点的值均小于等于一棵完全二叉树，任一个非终端结点的值均小于等于(或或大于等于大于等于)其左、右儿子结点的值。其左、右儿子结点的值。例，例，1285473053362491963811 98324根结点为最小值根结点为最小值根结点为最大值根结点为最大值堆排序第41页，本讲稿共70页2.把这棵普通的完全二

27、叉树改造成堆，便可获取把这棵普通的完全二叉树改造成堆，便可获取最小值最小值；思想:3.输出最小值输出最小值；4.删除根结点，继续改造剩余树成堆，便可获取删除根结点，继续改造剩余树成堆，便可获取次小值次小值；5.输出次小值输出次小值；6.重复改造，输出次次小值、次次次小值，直至所有结点均重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序输出，便得到一个排序。1.将序列构造成一棵完全二叉树将序列构造成一棵完全二叉树；第42页，本讲稿共70页例，序列 49 38 65 97 76 13 27 501.按顺序依次构造成完全二叉树的结点；按顺序依次构造成完全二叉树的结点；493865

28、97761327502.把完全二叉树改造成把完全二叉树改造成堆堆；从下向上，父子交换；从下向上，父子交换；50971365134949273.取得最小值取得最小值 134.删除删除 13，重新改造成新堆；，重新改造成新堆；1397279797495.取得次小值取得次小值 27；6.删除删除 27，重新改造成新堆；，重新改造成新堆；9727973897507.取得次次小值取得次次小值 38；第43页，本讲稿共70页归并排序（Merge Sort)|归并-合并两个有序的序列z假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2)z方法很简单

29、：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并，其复杂度为O(n)第44页，本讲稿共70页归并排序（Merge Sort)|归并-合并两个有序的序列A:1 3 8 9 11B:2 5 7 10 13C:C:1 2 2 3 5 7 8 98 9 10 11 13第45页，本讲稿共70页归并排序（Merge Sort)|归并-合并两个有序的序列void merge(T A,int Alen,T B,int Blen,T C)int i=0,j=0,k=0;while(i

30、Alen&j Blen)if(Ai Bj)Ck+=Ai+;else Ck+=Bj+;while(i Alen)Ck+=Ai+;while(j Blen)Ck+=Bj+;第46页，本讲稿共70页归并排序（Merge Sort)|归并-合并一个序列中的两个有序的数据段void merge(T A,int l,int m,int h)int i=l,j=m+1,k=0;T*C=new Th-l+1;while(i=m&j=h)if(Ai Aj)Ck+=Ai+;else Ck+=Aj+;while(i =m)Ck+=Ai+;while(j =h)Ck+=Bj+;for(k=0;kb和ab),z如果以每

31、次比较作为节点，则每个以比较为基础的排序算法都可以用一个二叉树来表示，其中一个中间节点表示一次比较，叶子节点表示排序的一种结果，这样的二叉树称为判定树或决策树z举例：比如有一个序列a,b,c(a,b,c互不相等），下列算法：先比较a和b,再比较a和c，最后比较b和c 可以用下面的判定树表示 第53页，本讲稿共70页归并排序（Merge Sort)|以比较为基础的排序算法的下界ab?ab?yesyesac?yesbc?yesabcabcacbnonononocabac?yesbacnobc?yesyesbcacbano第54页，本讲稿共70页归并排序（Merge Sort)|以比较为基础的排序算

32、法的下界z假设输入为a,b,c,acb,则算法执行经过的路线为(ab)(ac)(bc)，需要3次比较z假设输入为a,b,c,bac,则算法执行经过的路线为(ab)(ac)需要2次比较z任何以比较为基础的排序算法都可以表示为一棵决策树树的形状和大小表示的是排序算法的功能和需要排序的元素个数树的高度表示了算法的运行时间任何排序决策树都有n!个叶子 第55页，本讲稿共70页归并排序（Merge Sort)|以比较为基础的排序算法的下界z根据数据结构中关于二叉树的性质，有：z最坏情况：任何排序算法至少要做次比较z平均情况：任何排序算法的平均比较次数的下界是z结论：具有O(nlgn)复杂度的比较排序算法

33、在渐进意义下是最优的算法 第56页，本讲稿共70页是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。1.多关键字排序多关键字排序扑克牌问题扑克牌问题:已知扑克牌中已知扑克牌中52张牌面的次序关系定义为张牌面的次序关系定义为:花色:面值:2 3 A.例，例，8 3花色优先级更高，为主关键字，面值为次关键字基数排序第57页，本讲稿共70页2.52张牌排序方法:最高位优先法最高位优先法(MSDF):先按不同先按不同“花色花色”分成有次序的分成有次序的4堆，每一堆均具有相同的花色；堆，每一堆均具有相同的花色；然后分别对每一堆按然后分别对

34、每一堆按“面值面值”大小整理有序。大小整理有序。最低位优先法最低位优先法(LSDF):先按不同先按不同“面值面值”分成分成 13 堆堆；然后将这然后将这 13 堆牌自小至大叠在一起堆牌自小至大叠在一起(2,3,.,A)；然后将这付牌整个颠倒过来再重新按不同的然后将这付牌整个颠倒过来再重新按不同的“花色花色”分成分成 4 堆堆；最后将这最后将这 4 堆牌按自小至大的次序合在一起堆牌按自小至大的次序合在一起。收集分配第58页，本讲稿共70页3.基数排序基数排序就是借助于基数排序就是借助于“分配分配”和和“收集收集”两种操作实现对单逻辑关两种操作实现对单逻辑关键字的排序。键字的排序。首先，单逻辑关键

35、字通常都可以看作是由若干关键字复合而成。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。其次，利用其次，利用 LSDF 法实现对若干关键字的排序。法实现对若干关键字的排序。例，若关键字是数值，且值域为例，若关键字是数值，且值域为 0K999，故可以将故可以将 K 看作是由看作是由 3 个关键字个关键字 K0 K1 K2 组成，组成，例，例，603是由是由 6 0 3 组成。组成。第59页，本讲稿共70页例，序列 278 109 063 930 589 184 505 269 008 083第一趟分配第一趟分配0 1 2 3 4 5 6 7 8 9278 1090639305891845

36、05269008083第一趟收集第一趟收集930063 083184505278 008109 589 269第二趟分配第二趟分配0 1 2 3 4 5 6 7 8 9930063083184505278008109589269第二趟收集第二趟收集505 008 109930063 269278083 184 589第60页，本讲稿共70页第二趟收集505 008 109930063 269 278 083 184 589第三趟分配第三趟分配0 1 2 3 4 5 6 7 8 9505008 109930063269278083184589第三趟收集第三趟收集008 063 083109 18

37、4269 278505 589930第61页，本讲稿共70页中序遍历可实现二叉搜索树结点的有序化中序遍历可实现二叉搜索树结点的有序化 13 8523 1837 95 8 9 13 18 23 37?如何实现自大到小排列二叉树排序第62页，本讲稿共70页各种内排序方法的选择各种内排序方法的选择1从时间复杂度选择从时间复杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。2从空间复杂度选择从空间复杂度选择尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。3一般

38、选择规则一般选择规则（1）当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。第63页，本讲稿共70页（2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。（3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。（4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。(5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。第64页，本讲稿共70

39、页各种排序方法的比较各种排序方法的比较第65页，本讲稿共70页案例分析：多项式相加|C+中如何表示多项式z链表|对两个多项式中的每个数据项的变量进行排序|执行加法运算第66页，本讲稿共70页课堂练习|对于一组记录的排序码为(465，792，562，383，401，845，502，423)，写出基数排序（低位优先）进行一趟分配与回收后的结果。第67页，本讲稿共70页序列 8,3,10,13,25,18,6,4对上述序列使用直接插入排序、希尔排序（d1=4；d2=2;d3=1;）、快速排序、堆排序、归并排序、基数排序（低位优先）进行排序的过程。作业1第68页，本讲稿共70页作业2|P409：1，15第69页，本讲稿共70页上机作业1.直接插入排序程序2.希尔排序程序3.编写冒泡排序程序（改进版）4.快速排序程序5.简单选择排序程序6.归并排序程序第70页，本讲稿共70页