常用排序算法

常用排序算法第1页，共56页，2023年，2月20日，星期一内部排序:

指的是待排序记录存放在计算机随机存储器中进行的排序过程。外部排序:

指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。内部排序与外部排序第2页，共56页，2023年，2月20日，星期一假设Ki=Kj

，且排序前序列中Ri

领先于Rj

；若在排序后的序列中Ri

仍领先于Rj

，则称排序方法是稳定的。若在排序后的序列中Rj

仍领先于Ri

，则称排序方法是不稳定的。例，序列3158

869若排序后得368

8915稳定的若排序后得368

8915不稳定的排序衡量指标——稳定性第3页，共56页，2023年，2月20日，星期一排序衡量指标——时间复杂度排序过程主要是对记录的排序码进行比较和记录的移动过程。排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性等。第4页，共56页，2023年，2月20日，星期一按照排序过程中所依据的原则的不同可以分类为:插入排序交换排序(快速排序)选择排序归并排序基数排序二叉排序树排序内部排序第5页，共56页，2023年，2月20日，星期一思想:利用有序表的插入操作进行排序有序表的插入:

将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。例，序列132738657697插入4913273849

657697插入排序——直接插入排序第6页，共56页，2023年，2月20日，星期一直接插入排序——算法描述例，序列49386597761327初始，S={49}；{3849}初始，令第1

个元素作为初始有序表；依次插入第

2,3,…,k

个元素构造新的有序表；直至最后一个元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要应用比较和移动两种操作。第7页，共56页，2023年，2月20日，星期一voidInsert(ArrNode*pnum){for(i=1;i<Len;i++){ tmp=pnum[i]; for(j=i;j>0&&tmp.key<pnum[j-1].key;j--){ pnum[j]=pnum[j-1]; } pnum[j]=tmp; }}直接插入排序——算法描述第8页，共56页，2023年，2月20日，星期一时间复杂度分析：外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i＋2次（逆序）（i=1,2,…,n-1）。Cmin=n-1Mmin=2（n-1）Cmax=1+2+…+n-1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mmax=（n2+7n-8）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。直接插入排序的效率分析第9页，共56页，2023年，2月20日，星期一由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半查找操作。例，序列49386597761327设已形成有序表{3849659776}插入元素13折半插入排序第10页，共56页，2023年，2月20日，星期一voidBinaryInsertSort(ArrNode*pnum，intL){for(inti=1;i<L;i++)//共进行n-1次插入

{intleft=0,right=i-1;temp=pnum[i]; while(left<=right) {intmiddle=(left+right)/2;//取中点

if(temp<pnum[middle])right=middle-1;//取左区间

else left=middle+1;//取右区间

} for(intj=i-1;j>=left;j--) pnum[j+1]=pnum[j];//元素后移空出插入位

pnum[left]=temp;}}折半插入排序——算法描述第11页，共56页，2023年，2月20日，星期一折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。第12页，共56页，2023年，2月20日，星期一直接插入排序1.若待排序记录序列按关键字基本有序，则排序效率可大大提高；2.待排序记录总数越少，排序效率越高；希尔(shell)排序第13页，共56页，2023年，2月20日，星期一将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进行一次直接插入排序。例，序列493865977613274855419第一趟排序491319382765489755764131949273848655597476希尔(shell)排序——算法思想第14页，共56页，2023年，2月20日，星期一第二趟排序13194927384865559747613553876274

654948199713385576427

4965194897第三趟排序4131927

38

4849

556576

97第15页，共56页，2023年，2月20日，星期一voidHill(ArrNode*pnum,intincrement)//初始值为Lens{printf("\nTheHillSortlistis\n");for(h=increment;h>0;h=h/2){ for(j=h;j<Len;j++){ t=*(pnum+j); for(k=j-h;(k>=0&&t.key<pnum[k].key);k=k-h) *(pnum+k+h)=*(pnum+k); *(pnum+k+h)=t; } }}希尔(shell)排序——算法思想第16页，共56页，2023年，2月20日，星期一希尔排序效率分析希尔排序的时间复杂性在O（nlog2n）和O（n2

）之间，大致为O（n1.3）。第17页，共56页，2023年，2月20日，星期一思想:

通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；...直至比较第n-1个元素与第n个元素的大小，若为逆序，则交换；第一趟排序:结果:关键字最大的记录被交换至最后一个元素位置上。交换排序——冒泡排序第18页，共56页，2023年，2月20日，星期一例，序列4938761327493876132738

49

13

27384913762776初始第一趟排序后最大值13

492749次大值第二趟排序后3813

27132713382738第三趟排序后第四趟排序后第19页，共56页，2023年，2月20日，星期一voidBubble(ArrNode*pnum){for(i=0;i<Len-1;i++){ for(j=Len-1;j>i;j--){ if(pnum[j-1].key>pnum[j].key){ tmp=pnum[j]; pnum[j]=pnum[j-1]; pnum[j-1]=tmp; } }}}冒泡排序的算法实现第20页，共56页，2023年，2月20日，星期一从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n)/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。冒泡排序的效率分析第21页，共56页，2023年，2月20日，星期一冒泡排序的一种改进算法。思想:以首记录作为轴记录，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。(小值记录在前、大值记录在后)轴记录将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。直至整个序列有序。交换排序——快速排序第22页，共56页，2023年，2月20日，星期一快速排序—算法思想第23页，共56页，2023年，2月20日，星期一3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49快速排序—算法思想第24页，共56页，2023年，2月20日，星期一

voidQuick(ArrNode*pnum,intlow,inthigh){inti=low,j=high;ArrNodekey;key=pnum[i];if(i>=j)return;while(i<j){ while(i<j&&pnum[j].key>key.key) j--; if(i<j){ pnum[i]=pnum[j]; i++;}快速排序—算法思想第25页，共56页，2023年，2月20日，星期一

while(i<j&&pnum[i].key<key.key) i++; if(i<j){ pnum[j]=pnum[i]; j--; }}pnum[i]=key;printf("\n");Quick(pnum,low,j-1);Quick(pnum,j+1,high);}快排序---分割过程伪码第26页，共56页，2023年，2月20日，星期一快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2n<h<log2n+1，所以总的比较次数不会超过(n+1)log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1≤i≤n）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。第27页，共56页，2023年，2月20日，星期一思想:

每一趟都选出一个最大或最小的元素，并放在合适当的位置。简单选择排序树形选择排序堆排序选择排序第28页，共56页，2023年，2月20日，星期一思想:

第1趟选择:从1—n

个记录中选择关键字最小的记录，并和第1个记录交换。第2趟选择:从2—n

个记录中选择关键字最小的记录，并和第2

个记录交换。第n-1趟选择:从n-1—n

个记录中选择关键字最小的记录，并和第n-1

个记录交换。...简单选择排序第29页，共56页，2023年，2月20日，星期一例，序列4938976576第1趟选择:min3849976576第2趟选择:min38

49976576第3趟选择:min38

49

659776第4趟选择:min38

49

65

7697第30页，共56页，2023年，2月20日，星期一voidChoise(ArrNode*pnum){for(i=0;i<Len-1;i++){ minLoc=i; for(j=i+1;j<Len;j++){ if(pnum[minLoc].key>pnum[j].key) minLoc=j; } if(i!=minLoc){ tmp=pnum[minLoc]; pnum[minLoc]=pnum[i]; pnum[i]=tmp; }}}直接选择排序的伪码描述第31页，共56页，2023年，2月20日，星期一选择排序的主要操作是进行关键字间的比较。在n个关键字中选出最小值，至少需要n-1次比较。在剩余的n-1个关键字中选出最小值，至少需要n-2次比较？如果能利用前n-1次比较所得信息，可以减少后面选择的比较次数。第32页，共56页，2023年，2月20日，星期一例，序列4938659776132750第一趟选择133813493865977613275038651327最小值树形选择排序第33页，共56页，2023年，2月20日，星期一第二趟选择2738274938659776∞275038657627次小值第三趟选择3838504938659776∞∞5038657650次次小值49386597761327504938659776∞2750缺点:

需要大量辅助存储空间，最大值多余比较第34页，共56页，2023年，2月20日，星期一堆:

一棵完全二叉树，任一个非终端结点的值均小于等于(或大于等于)其左、右子树结点的值。1285473053362491963811

98324小顶堆大顶堆堆排序第35页，共56页，2023年，2月20日，星期一2.把这棵普通的完全二叉树改造成堆，便可获取最小值；堆排序算法思想:3.输出最小值；4.删除根结点，继续改造剩余树成堆，便可获取次小值；5.输出次小值；6.重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序。1.将序列构造成一棵完全二叉树；尽可能减少存储空间开销，让待排序的记录仅占最小的空间（1个）第36页，共56页，2023年，2月20日，星期一例，序列49386597761327501.按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成堆；从下向上，父子交换；50971365134949273.取得最小值134.删除13

，重新改造成新堆；1397279797495.取得次小值27；6.删除27

，重新改造成新堆；9727973897507.取得次次小值38；第37页，共56页，2023年，2月20日，星期一堆排序算法思想:voidHeap(ArrNode*pnum,intL){inti,k;ArrNodet;for(i=L/2-1;i>=0;i--) createheap(pnum,i,L); //Thebasicheapfor(k=L-1;k>0;k--){ t=*pnum; *pnum=*(pnum+k); *(pnum+k)=t; createheap(pnum,0,k);}}第38页，共56页，2023年，2月20日，星期一堆排序算法思想:voidcreateheap(ArrNode*pnum,inti,intnLens){intnChild,nTemp;for(nTemp=pnum[i].key;2*i+1<nLens;i=nChild){ nChild=2*i+1; if((nChild!=nLens-1) &&(pnum[nChild+1].key>pnum[nChild].key)) ++nChild; if(nTemp<pnum[nChild].key) pnum[i]=pnum[nChild]; else break;}pnum[i].key=nTemp;}第39页，共56页，2023年，2月20日，星期一归并排序（MergeSort)归并---合并两个有序的序列假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2)方法：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并，其复杂度为O(n)第40页，共56页，2023年，2月20日，星期一归并---合并两个有序的序列A:138911B:2571013归并排序（MergeSort)C:1

2

3

5

7

89

10

11

13第41页，共56页，2023年，2月20日，星期一voidmerge(TA[],intAlen,TB[],intBlen,TC[]){inti=0,j=0,k=0;while(i<Alen&&j<Blen){if(A[i]<B[j]) C[k++]=A[i++]; else C[k++]=B[j++]; } while(i<Alen) C[k++]=A[i++]; while(j<Blen) C[k++]=B[j++];}归并排序（MergeSort)第42页，共56页，2023年，2月20日，星期一归并---合并一个序列中的两个有序的数据段voidmerge(TA[],intl,intm,inth){inti=l,j=m+1,k=0;T*C=newT[h-l+1];while(i<=m&&j<=h){if(A[i]<A[j])C[k++]=A[i++]; elseC[k++]=A[j++];} while(i<=m)C[k++]=A[i++]; while(j<=h)C[k++]=B[j++];for(k=0;k<h-l+1;k++)A[i+k]=C[k];//将排好序的元素写回A数组

delete[]C;}第43页，共56页，2023年，2月20日，星期一归并排序（MergeSort)归并排序归并排序是一个分治递归算法递归基础：若序列只有一个元素，则它是有序的，不执行任何操作递归步骤：先把序列划分成长度基本相等的两个序列对每个子序列递归排序把排好序的子序列归并成最后的结果第44页，共56页，2023年，2月20日，星期一归并排序（MergeSort)初始序列：[8，4，5，6，2，1，7，3]分解：[8][4][5][6][2][1][7][3]归并：[4，8][5，6][1，2][3，7]归并：[4，5，6，8][1，2，3，7]归并：[1，2，3，4，5，6，7，8]分解：[8，4，5，6][2，1，7，3]分解：[8，4][5，6][2，1][7，3]第45页，共56页，2023年，2月20日，星期一归并排序（MergeSort)算法分析最坏情况：归并排序是一个递归算法，所以很容易得到算法计算量的递推公式

所以算法最坏情况的复杂度为算法需要的辅助空间

第46页，共56页，2023年，2月20日，星期一以比较为基础的排序算法的下界根据数据结构中关于二叉树的性质，有：最坏情况：任何排序算法至少要做 次比较平均情况：任何排序算法的平均比较次数的下界是结论：具有O(nlgn)复杂度的比较排序算法在渐进意义下是最优的算法归并排序（MergeSort)第47页，共56页，2023年，2月20日，星期一一种借助多关键字排序的思想对单逻辑关键字进行排序的方法1.多关键字排序扑克牌问题:已知扑克牌中52张牌面的次序关系定义为:♣

＜

♦

＜

♥

＜

♠花色:面值:2＜3＜＜A...例，♦8

♠

3＜花色优先级更高，为主关键字，面值为次关键字基数排序第48页，共56页，2023年，2月20日，星期一2.52张牌排序方法:最高位优先法(MSDF):先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；然后分别对每一堆按“面值”大小整理有序。最低位优先法(LSDF):先按不同“面值”分成13堆；然后将这13堆牌自小至大叠在一起(2,3,...,A)；然后将这付牌整个颠倒过来再重新按不同的“花色”分成4堆；最后将这4堆牌按自小至大的次序合在一起。收集分配第49页，共56页，2023年，2月20日，星期一3.基数排序基数排序就是借助于“分配”和“收集”两种操作实现对单逻辑关键字的排序。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。其次，利用LSDF法实现对若干关键字的排序。例，若关键字是数值，且值域为0≤K≤999，故可以将K

看作是由3个关键字K0K1K2

组成，例，603是由603

组成。第50页，共56页，2023年，2月20日，星期一例，序列278109063