常用排序算法精选PPT.ppt

《常用排序算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《常用排序算法精选PPT.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、常用排序算法第1页，此课件共56页哦内部排序内部排序:指的是待排序记录存放在计算机指的是待排序记录存放在计算机随机存储器随机存储器中中进行的排序过程。进行的排序过程。外部排序外部排序:指的是待排序记录的数量很大，以致内存一次不能容指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对纳全部记录，在排序过程中尚需对外存外存进行访问的排序过程。进行访问的排序过程。内部排序与外部排序内部排序与外部排序第2页，此课件共56页哦假设假设 Ki=Kj，且排序前序列中，且排序前序列中 Ri 领先于领先于 Rj；若在排序后的序列中若在排序后的序列中 Ri 仍领先于仍领先于 Rj，则称排序

2、方法是，则称排序方法是稳定的稳定的。若在排序后的序列中若在排序后的序列中 Rj 仍领先于仍领先于 Ri，则称排序方法是，则称排序方法是不稳定不稳定的的。例，序列例，序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15稳定的稳定的若排序后得若排序后得 3 6 8 8 9 15不稳定的不稳定的排序衡量指标排序衡量指标稳定性稳定性第3页，此课件共56页哦排序衡量指标排序衡量指标时间复杂度时间复杂度排序过程主要是对记录的排序码进行比较和记录的移动过程。排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次

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

4、到一个新的有序表。例，序列例，序列 13 27 38 65 76 97 插入插入 4913 27 38 49 65 76 97插入排序插入排序直接插入排序直接插入排序第6页，此课件共56页哦直接插入排序直接插入排序算法描述算法描述例，序列例，序列 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

5、65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用直接插入排序算法主要应用比较比较和和移动移动两种操作。两种操作。第7页，此课件共56页哦void Insert(ArrNode*pnum)for(i=1;i 0&tmp.key pnumj-1.key;j-)pnumj=pnumj-1;pnumj=tmp;直接插入排序直接插入排序算法描述算法描述第8页，此课件共56页哦时间复杂度分析：外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1,2,n-1）。Cmin=n-1 M min=2（n-1）Cmax=1+

6、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页，此课件共56页哦由于直接插入排序算法利用了有序表的插入操作，故由于直接插入排序算法利用了有序表的插入操作，故顺序查找顺序查找操作可以替换为操作可以替换为折半查找折半查找操作。操作。例，序列例，序列 49 38 65 97 76 13 27 设已形成有序表设已形成有序表 38 49 65 97 76 插入元

7、素插入元素 13折半插入排序折半插入排序第10页，此课件共56页哦void BinaryInsertSort(ArrNode*pnum，int L)for(int i=1;iL;i+)/共进行共进行n-1次插入次插入 int left=0,right=i-1;temp=pnumi;while(left=right)int middle=(left+right)/2;/取中点取中点 if(temp=left;j-)pnumj+1=pnumj;/元素后移空出插入位元素后移空出插入位 pnumleft=temp;折半插入排序折半插入排序算法描述算法描述第11页，此课件共56页哦折半插入效率分析折半插

8、入效率分析折半插入效率分析折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。第12页，此课件共56页哦直接插入排序直接插入排序1.若待排序记录序列按关键字若待排序记录序列按关键字基本有序基本有序，则排序效率可，则排序效率可大大提高；大大提高；2.待排序记录总数越少，排序效率越高；待排序记录总数越少，排序效率越高；希尔希尔(shell)排序排序第13页，此

9、课件共56页哦将待排序记录序列分割成为若干子序列分别进行直接插入排序；将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进行一次直接插入排序。待整个序列中的记录基本有序后，再全体进行一次直接插入排序。例，序列例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76希尔希尔(shell)排序排序算法思想算法思想第14页，此课件共56页哦第二趟排序第二趟排序13 19 4927 3848 6555 974 761

10、3 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页，此课件共56页哦void Hill(ArrNode*pnum,int increment)/初始值为初始值为Lens printf(nThe Hill Sort list is n);for(h=increment;h 0;h=h/2)for(j=h;j=0&t.key pnumk.key);k=k-h)*(pnum+k+h)=*(pnum+k);*(pnum+k+h)=t;希尔希尔(she

11、ll)排序排序算法思想算法思想第16页，此课件共56页哦希尔排序效率分析希尔排序效率分析希尔排序的时间复杂性在O（nlog2n）和O（n2）之间，大致为O（n1.3）。）。第17页，此课件共56页哦思想思想:通过不断比较相邻元素大小，进行交换来实现排序。通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；首先将第一个元素与第二个元素比较大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；.直至比较第直至比较第 n-1 个元素与第个元素与第 n 个元素的大小，若为

12、逆序，则交换；个元素的大小，若为逆序，则交换；第一趟排序第一趟排序:结果结果:关键字最大关键字最大的记录被交换至的记录被交换至最后最后一个元素位置上。一个元素位置上。交换排序交换排序冒泡排序冒泡排序第18页，此课件共56页哦例，序列例，序列 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页，此课件共56页哦void Bubble(A

13、rrNode*pnum)for(i=0;i i;j-)if(pnumj-1.key pnumj.key)tmp=pnumj;pnumj=pnumj-1;pnumj-1=tmp;冒泡排序的算法实现冒泡排序的算法实现第20页，此课件共56页哦从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳

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

15、列有序。直至整个序列有序。交换排序交换排序快速排序快速排序第22页，此课件共56页哦快速排序快速排序算法思想算法思想第23页，此课件共56页哦38 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 4927lowlow27 38 97 76 13 4965highhigh27 38 97 76 65 4913lowlow27 38 13 76 65 4997highhigh49快速排序快速排序算法思想算法思想第24页，此课件共56页哦 void Quick

16、(ArrNode*pnum,int low,int high)int i=low,j=high;ArrNode key;key=pnumi;if(i=j)return;while(i j)while(i key.key)j-;if(i j)pnumi=pnumj;i+;快速排序快速排序算法思想算法思想第25页，此课件共56页哦while(i j&pnumi.key key.key)i+;if(i j)pnumj=pnumi;j-;pnumi=key;printf(n);Quick(pnum,low,j-1);Quick(pnum,j+1,high);快排序快排序-分割过程伪码分割过程伪码第26

17、页，此课件共56页哦快速排序的效率分析快速排序的效率分析若若快快速速排排序序出出现现最最好好的的情情形形（左左、右右子子区区间间的的长长度度大大致致相相等等），则则结结点点数数n与与二二叉叉树树深深度度h应应满满足足log2nhlog2n+1，所所以以总总的的比比较较次次数数不不会会超超过过(n+1)log2n。因因此此，快快速速排排序序的的最最好好时时间间复复杂杂度度应应为为O（nlog2n）。而而且且在在理理论论上上已已经经证证明明，快快速速排排序序的的平平均均时时间间复复杂杂度度也也为为O（nlog2n）。）。若若快快速速排排序序出出现现最最坏坏的的情情形形（每每次次能能划划分分成成两两

18、个个子子区区间间，但但其其中中一一个个是是空空），则则这这时时得得到到的的二二叉叉树树是是一一棵棵单单分分枝枝树树，得得到到的的非非空空子子区区间间包包含含有有n-i个个(i代代表表二二叉叉树树的的层层数数（1in）元元素素，每每层层划划分分需需要要比比较较n-i+2次次，所所以以总总的的比比较次数为（较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为。因此，快速排序的最坏时间复杂度为O(n2)。快快速速排排序序所所占占用用的的辅辅助助空空间间为为栈栈的的深深度度，故故最最好好的的空空间间复复杂杂度度为为O（log2n），最坏的空间复杂度为），最坏的空间复杂度为O(n)。快速排序

19、是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。第27页，此课件共56页哦思想思想:每一趟都选出一个最大或最小的元素，并每一趟都选出一个最大或最小的元素，并放在合适当的位置。放在合适当的位置。简单选择排序简单选择排序 树形选择排序树形选择排序 堆排序堆排序选择排序选择排序第28页，此课件共56页哦思想思想:第第 1 趟选择趟选择:从从 1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 1 个记录个记录交换。交换。第第 2 趟选择趟选择:从从 2n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 2 个记录交换。个记录交换。第第n-

20、1趟选择趟选择:从从 n-1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 n-1 个记录交换。个记录交换。.简单选择排序简单选择排序第29页，此课件共56页哦例，序列例，序列 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第30页，此课件共56页哦void Choise(ArrNode*pnum)for(i=0;i Len-1;i+)minLoc=i;

21、for(j=i+1;j pnumj.key)minLoc=j;if(i!=minLoc)tmp=pnumminLoc;pnumminLoc=pnumi;pnumi=tmp;直接选择排序的伪码描述直接选择排序的伪码描述直接选择排序的伪码描述直接选择排序的伪码描述第31页，此课件共56页哦选择排序的主要操作是进行关键字间的选择排序的主要操作是进行关键字间的比较比较。在在 n 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-1 次比较次比较。在剩余的在剩余的 n-1 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-2 次比次比较较？如果能利用前如果能利用前 n-1

22、 次比较所得信息，可以减少后面选择的比较次比较所得信息，可以减少后面选择的比较次数。次数。第32页，此课件共56页哦例，序列例，序列 49 38 65 97 76 13 27 50第一趟选择第一趟选择133813493865977613275038651327最小值最小值树形选择排序树形选择排序第33页，此课件共56页哦第二趟选择第二趟选择2738274938659776275038657627次小值次小值第三趟选择第三趟选择38385049386597765038657650次次小值次次小值493865977613275049386597762750缺点缺点:需要大需要大量辅助存储空间，量辅

23、助存储空间，最大值多余比较最大值多余比较第34页，此课件共56页哦堆堆:一棵完全二叉树，任一个非终端结点的值均小于等一棵完全二叉树，任一个非终端结点的值均小于等于于(或大于等于或大于等于)其左、右子树结点的值。其左、右子树结点的值。1285473053362491963811 98324小顶堆小顶堆大顶堆大顶堆堆排序堆排序第35页，此课件共56页哦2.把这棵普通的完全二叉树改造成堆，便可获取把这棵普通的完全二叉树改造成堆，便可获取最小值最小值；堆排序算法思想堆排序算法思想:3.输出最小值输出最小值；4.删除根结点，继续改造剩余树成堆，便可获取删除根结点，继续改造剩余树成堆，便可获取次小值次小值

24、；5.输出次小值输出次小值；6.重复改造，输出次次小值、次次次小值，直至所有结点均重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序输出，便得到一个排序。1.将序列构造成一棵完全二叉树将序列构造成一棵完全二叉树；尽可能减少存储空间开销，让待排序的记录仅占尽可能减少存储空间开销，让待排序的记录仅占最小的空间（最小的空间（1 1个）个）第36页，此课件共56页哦例，序列例，序列 49 38 65 97 76 13 27 501.按顺序依次构造成完全二叉树的结点；按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成把完全二叉树改造成堆堆；从下向

25、上，父子交换；从下向上，父子交换；50971365134949273.取得最小值取得最小值 134.删除删除 13，重新改造成新堆；，重新改造成新堆；1397279797495.取得次小值取得次小值 27；6.删除删除 27，重新改造成新堆；，重新改造成新堆；9727973897507.取得次次小值取得次次小值 38；第37页，此课件共56页哦堆排序算法思想堆排序算法思想:void Heap(ArrNode*pnum,int L)int i,k;ArrNode t;for(i=L/2-1;i=0;i-)createheap(pnum,i,L);/The basic heap for(k=L-1

26、;k 0;k-)t=*pnum;*pnum=*(pnum+k);*(pnum+k)=t;createheap(pnum,0,k);第38页，此课件共56页哦堆排序算法思想堆排序算法思想:void createheap(ArrNode*pnum,int i,int nLens)int nChild,nTemp;for(nTemp=pnumi.key;2*i+1 pnumnChild.key)+nChild;if(nTemp pnumnChild.key)pnumi=pnumnChild;else break;pnumi.key=nTemp;第39页，此课件共56页哦归并排序（归并排序（Merge

27、 Sort)|归并归并-合并两个有序的序列合并两个有序的序列z假设有两个已排序好的序列假设有两个已排序好的序列A（长度为（长度为n1），），B（长度为（长度为n2），），将它们合并为一个有序的序列将它们合并为一个有序的序列C（长度为（长度为n=n1+n2)z方法：把方法：把A，B两个序列的最小元素进行比较，把其中较小的两个序列的最小元素进行比较，把其中较小的元素作为元素作为C的第一个元素；在的第一个元素；在A，B剩余的元素中继续挑最小的元剩余的元素中继续挑最小的元素进行比较，确定素进行比较，确定C的第二个元素，依次类推，就可以完成对的第二个元素，依次类推，就可以完成对A和和B的归并，的归并，其

28、复杂度为其复杂度为O(n)第40页，此课件共56页哦|归并归并-合并两个有序的序列合并两个有序的序列A:1 3 8 9 11B:2 5 7 10 13归并排序（归并排序（Merge Sort)C:1 2 3 5 7 8 9 10 11 13第41页，此课件共56页哦void merge(T A,int Alen,T B,int Blen,T C)int i=0,j=0,k=0;while(i Alen&j Blen)if(Ai Bj)Ck+=Ai+;else Ck+=Bj+;while(i Alen)Ck+=Ai+;while(j Blen)Ck+=Bj+;归并排序（归并排序（Merge So

29、rt)第42页，此课件共56页哦|归并-合并一个序列中的两个有序的数据段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;kh-l+1;k+)Ai+k=Ck;/将排好序的元素写回将排好序的元素写回A数组数组 delete C;第43页，此课件共56页哦归并排序（归并排序（Merge Sort)|归并排序归并排序z归并排序是一个分治递归算

30、法归并排序是一个分治递归算法递归基础：若序列只有一个元素，则它是有序的，不执行递归基础：若序列只有一个元素，则它是有序的，不执行任何操作任何操作递归步骤：递归步骤：l先把序列划分成长度基本相等的两个序列先把序列划分成长度基本相等的两个序列l对每个子序列递归排序对每个子序列递归排序l把排好序的子序列归并成最后的结果把排好序的子序列归并成最后的结果第44页，此课件共56页哦归并排序（归并排序（Merge Sort)初始序列：初始序列：初始序列：初始序列：88，4 4，5 5，6 6，2 2，1 1，7 7，33分解：8 4 5 6 2 1 7 3归并：4，8 5，6 1，2 3，7归并：4，5，6

31、，8 1，2，3，7归并：归并：归并：归并：11，2 2，3 3，4 4，5 5，6 6，7 7，88分解：8，4，5，6 2，1，7，3分解：8，4 5，6 2，1 7，3第45页，此课件共56页哦归并排序（归并排序（Merge Sort)|算法分析z最坏情况：归并排序是一个递归算法，所以很容易得到算法计算量的递推公式 所以算法最坏情况的复杂度为z算法需要 的辅助空间 第46页，此课件共56页哦|以比较为基础的排序算法的下界z根据数据结构中关于二叉树的性质，有：z最坏情况：任何排序算法至少要做次比较z平均情况：任何排序算法的平均比较次数的下界是z结论：具有O(nlgn)复杂度的比较排序算法在

32、渐进意义下是最优的算法归并排序（归并排序（Merge Sort)第47页，此课件共56页哦一种借助多关键字排序的思想对单逻辑关键字进行排序的方法一种借助多关键字排序的思想对单逻辑关键字进行排序的方法 1.多关键字排序多关键字排序扑克牌问题扑克牌问题:已知扑克牌中已知扑克牌中52张牌面的次序关系定义为张牌面的次序关系定义为:花色花色:面值面值:2 3 A.例，例，8 3花色优先级更高，为花色优先级更高，为主关键字，面值为次主关键字，面值为次关键字关键字基数排序基数排序第48页，此课件共56页哦2.52张牌排序方法张牌排序方法:最高位优先法最高位优先法(MSDF):先按不同先按不同“花色花色”分成

33、有次序的分成有次序的4堆，每一堆均具有相同的花色；堆，每一堆均具有相同的花色；然后分别对每一堆按然后分别对每一堆按“面值面值”大小整理有序。大小整理有序。最低位优先法最低位优先法(LSDF):先按不同先按不同“面值面值”分成分成 13 堆堆；然后将这然后将这 13 堆牌自小至大叠在一起堆牌自小至大叠在一起(2,3,.,A)；然后将这付牌整个颠倒过来再重新按不同的然后将这付牌整个颠倒过来再重新按不同的“花色花色”分成分成 4 堆堆；最后将这最后将这 4 堆牌按自小至大的次序合在一起堆牌按自小至大的次序合在一起。收集收集分配分配第49页，此课件共56页哦3.基数排序基数排序基数排序就是借助于基数排

34、序就是借助于“分配分配”和和“收集收集”两种操作实现对单逻辑两种操作实现对单逻辑关键字的排序。关键字的排序。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。其次，利用其次，利用 LSDF 法实现对若干关键字的排序。法实现对若干关键字的排序。例，若关键字是数值，且值域为例，若关键字是数值，且值域为 0K999，故可以将故可以将 K 看作是由看作是由 3 个关键字个关键字 K0 K1 K2 组成，组成，例，例，603是由是由 6 0 3 组成。组成。第50页，此课件共56页哦例，序列例，序列 278 109 063 930 589 1

35、84 505 269 008 083第一趟分配第一趟分配0 1 2 3 4 5 6 7 8 9278 109063930589184505269008083第一趟收集第一趟收集930063 083184505278 008109 589 269第二趟分配第二趟分配0 1 2 3 4 5 6 7 8 9930063083184505278008109589269第二趟收集第二趟收集505 008 109930063 269278083 184 589第51页，此课件共56页哦第二趟收集第二趟收集505 008 109930063 269278083 184 589第三趟分配第三趟分配0 1 2

36、3 4 5 6 7 8 9505008 109930063269278083184589第三趟收集第三趟收集008 063 083109 184269 278505 589930第52页，此课件共56页哦中序遍历可实现二叉搜索树结点的有序化中序遍历可实现二叉搜索树结点的有序化 13 8523 1837 95 8 9 13 18 23 37?如何实现自如何实现自大到小排列大到小排列二叉树排序二叉树排序第53页，此课件共56页哦各种内排序方法的选择各种内排序方法的选择1从时间复杂度选择从时间复杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。2从

37、空间复杂度选择从空间复杂度选择尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。3一般选择规则一般选择规则（1）当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。第54页，此课件共56页哦(2)当当待待排排序序元元素素的的个个数数n大大，内内存存空空间间允允许许，且且要要求求排排序序稳稳定定时，则采用二路归并排序为宜。时，则采用二路归并排序为宜。(3)当当待待排排序序元元素素的的个个数数n大大，排排序序码码分分布布可可能能会会出出现现正正序序或或逆逆序序的的情情形形，且且对对稳稳定定性性不不做做要要求求时时，则则采采用用堆堆排排序序或或二二路路归归并并排排序序为为宜。宜。(4)当当待待排排序序元元素素的的个个数数n小小，元元素素基基本本有有序序或或分分布布较较随随机机，且且要求稳定时，则采用直接插入排序为宜。要求稳定时，则采用直接插入排序为宜。(5)当当待待排排序序元元素素的的个个数数n小小，对对稳稳定定性性不不做做要要求求时时，则则采采用用直直接接选选择择排排序序为为宜宜，若若排排序序码码不不接接近近逆逆序序，也也可可以以采采用用直直接接插插入入排排序序。冒泡排序一般很少采用。冒泡排序一般很少采用。第55页，此课件共56页哦第56页，此课件共56页哦