排序算法详解

排序算法详解第1页，共68页，2023年，2月20日，星期一问题的提出：为什么要排序？有序表的优点？缺点？构造关系。按照什么原则排序？比较？如何进行排序？第2页，共68页，2023年，2月20日，星期一基本概念排序（Sorting）：简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕18女第3页，共68页，2023年，2月20日，星期一作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。排序码不一定是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。参与排序的对象，称为记录。一个记录可以包含多个字段。如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。排序码与关键码（primarykey）第4页，共68页，2023年，2月20日，星期一排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。

本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。排序的类型第5页，共68页，2023年，2月20日，星期一排序算法的评价评价排序算法好坏的标准执行算法所需的时间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数（必须）。算法执行中的移动次数（有可能避免）。通常会关注最坏情况和平均情况的开销。第6页，共68页，2023年，2月20日，星期一插入排序基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x

顺次选取一个元素插入到合适位置第7页，共68页，2023年，2月20日，星期一插入排序的细分类如何插入到已排好序的序列中？直接插入（从后向前找位置后插入）

O(n2)

二分法插入（按二分法找位置后插入）

O(nlog2n)

表插入排序（按链表查找位置后插入）

O(n2)第8页，共68页，2023年，2月20日，星期一直接插入排序基本思想：假定前面m个元素已经排序；取第(m+1)个元素，插入到前面的适当位置；一直重复，到m=n为止。（初始情况下，m=1）第9页，共68页，2023年，2月20日，星期一

第一趟：{23}，[起始只有一个记录]{11,23}11

第二趟：{11，23}，{11，23，55}55

第三趟：{11，23，55}，{11，23，55，97}97

第四趟：{11，23，55，97}，{11，19，23，55，97}19

第五趟：{11，19，23，55，97}，{11，19，23，55，80，97}80示例：{23，11，55，97，19，80}第10页，共68页，2023年，2月20日，星期一直接插入排序的算法中记录的数据结构typedefintKeyType;typedefintDataType;typedefstruct{

KeyTypekey; /*排序码字段*/DataTypeinfo;/*记录的其他字段*/}RecordNode;typedefstruct{ intn;/*n为文件中的记录个数，n<MAXNUM*/RecordNode*record;}SortObject;第11页，共68页，2023年，2月20日，星期一直接插入排序算法复杂度评价极端情况下：最小比较次数∶每个记录仅比较一次最大比较次数∶每个记录比较已排好序的记录长度第12页，共68页，2023年，2月20日，星期一直接插入排序算法评价2最小移动次数∶最大移动次数∶第13页，共68页，2023年，2月20日，星期一直接插入排序算法评价3初始数据状态相关：文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则算法的时间复杂度为O(n)若初态为反序，则时间复杂度为O(n2)第14页，共68页，2023年，2月20日，星期一直接插入排序算法评价4——平均复杂度插入记录Ri-1，有i种可能的插入位置，即插入到第0，1，…，i-1位置上，假设每种情况发生的概率是相等的，均为pj=1/i(j=0,1,…,i-1)比较次数为Cj=j+1(j=0,…,i-2,i-2)，则插入记录Ri-1的平均比较次数为∶第15页，共68页，2023年，2月20日，星期一直接插入排序算法评价5——平均复杂度直接插入排序的总的比较次数为：第16页，共68页，2023年，2月20日，星期一直接插入排序算法评价直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)直接插入排序的平均时间复杂度为T(n)=O(n2)算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)直接插入排序是稳定的第17页，共68页，2023年，2月20日，星期一存储结构与算法优化顺序存储结构：二分插入算法，减少比较次数。链式存储结构：减少移动次数。第18页，共68页，2023年，2月20日，星期一二分法插入排序特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序限制：必须采用顺序存储方式。第19页，共68页，2023年，2月20日，星期一例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42

lowmidhigh

[1527365369]42

lowhigh

mid

[1527365369]42

highlow[152736425369](high<low，查找结束，插入位置为low或high+1)(42>36)(42<53)第20页，共68页，2023年，2月20日，星期一二分法插入排序算法voidbinSort(SortObject*pvector){

inti,j,left,mid,right;

RecordNodetemp;

for(i=1;i<pvector->n;i++)

{

temp=pvector->record[i];

left=0;right=i–1;

while(left<=right)

{

mid=(left+right)/2；if(temp.key<vector->record[mid].key)

right=mid-1;

else left=mid+1;}//while

for(j=i-1;j>=left;j--)pvector->record[j+1]=pvector->record[j]; if(left!=i)pvector->record[left]=temp;}//for}//binSort第21页，共68页，2023年，2月20日，星期一二分插入排序比较次数二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数，插入第i个记录时，如果，则无论排序码的大小，都恰好经过次比较才能确定插入位置，如果，则比较次数为j+1，因此，将n(n=2k)个记录排序的总比较次数为第22页，共68页，2023年，2月20日，星期一二分法插入排序方法性能分析当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数算法的移动次数与直接插入排序算法的相同最坏的情况为n2/2最好的情况为n平均移动次数为O(n2)二分法插入排序算法的平均时间复杂度为T(n)=O(n2)二分插入排序法是稳定的排序算法,在检索时采用left>right结束，left、right的修改原则是：temp.key<pvector->record[mid].key，保证排序是稳定的。第23页，共68页，2023年，2月20日，星期一结论移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)二分法插入排序算法的平均时间复杂度为T(n)=O(n2)二分法插入排序是稳定的第24页，共68页，2023年，2月20日，星期一表插入排序表插入排序是在直接插入排序的基础上减少移动的次数。基本思想:在记录中设置一个指针字段，记录用链表连接插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表。第25页，共68页，2023年，2月20日，星期一structNode; /*单链表结点类型*/typedefstructNodeListNode;structNode{KeyTypekey; /*排序码字段*/DataTypeinfo; /*记录的其它字段*/ListNode*next; /*记录的指针字段*/};typedefListNode*LinkList;表插入算法中记录的数据结构第26页，共68页，2023年，2月20日，星期一表插入排序的算法性能分析

第i趟排序：最多比较次数i次，最少比较次数1次。

n-1趟总的比较次数：最多：最少：n-1

记录移动次数：0

时间效率：O(n2)

辅助空间：O(n)[指针]

稳定性：p->key<=now->key保证稳定的排序。第27页，共68页，2023年，2月20日，星期一选择排序思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。关键问题：在剩余的待排序记录序列中找到最小关键码记录。方法：直接选择排序堆排序。第28页，共68页，2023年，2月20日，星期一直接选择排序方法是∶首先在所有记录中选出排序码最小的记录，与第一个记录交换然后在其余的记录中再选出排序码最小的记录与第二个记录交换以此类推，直到所有记录排好序第29页，共68页，2023年，2月20日，星期一直接选择排序性能分析选择排序的比较次数与记录的初始状态无关。第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较。总的比较次数：移动次数：Mmin=0(初始为正序时）最多移动次数：Mmax=3(n-1)(初始为逆序时，每趟1次交换，3次移动完成）

时间复杂度：T(n)=O(n2)，辅助空间1个记录单位：Temp，稳定性：不稳定的排序。

第30页，共68页，2023年，2月20日，星期一31起泡排序方法先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换然后对新的第二个记录R1与第三个记录R2作同样的处理依次类推，直到处理完第n-1个记录和第n个记录从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡经过这次起泡，n个记录中最大者被安置在第n个位置上第31页，共68页，2023年，2月20日，星期一32此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。然后再对前n-2个记录重复上述过程……，这样最多做n-1次起泡就能完成排序可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序起泡排序方法第32页，共68页，2023年，2月20日，星期一若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶起泡排序的算法评价第33页，共68页，2023年，2月20日，星期一起泡排序的算法评价(续)起泡排序最好时间复杂度是O(n)起泡排序最坏时间复杂度为O(n2)起泡排序平均时间复杂度为O(n2)起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)起泡排序是稳定的第34页，共68页，2023年，2月20日，星期一归并排序（mergesort）归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是:只含一个记录的序列显然是个有序序列，经过"逐趟归并"使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。

第35页，共68页，2023年，2月20日，星期一归并排序（mergesort）88149825625279302331DivideandConquer第36页，共68页，2023年，2月20日，星期一MergeSort88149825625279302331SplitSetintoTwo

(norealwork)25,31,52,88,98Getonefriendto

sortthefirsthalf.14,23,30,62,79Getonefriendto

sortthesecondhalf.第37页，共68页，2023年，2月20日，星期一MergeSortMergetwosortedlistsintoone25,31,52,88,9814,23,30,62,7914,23,25,30,31,52,62,79,88,98第38页，共68页，2023年，2月20日，星期一第39页，共68页，2023年，2月20日，星期一二路归并算法的基本思路：两组归并算法merge：按low,m,high归并两组记录。结果放于low,high之间。voidmerge(RecordNode*r,RecordNode*r1,intlow,intm,inthigh)一趟归并算法mergePass：两两归并长度为length的一组记录：voidmergePass(RecordNode*r,RecordNode*r1,intn,intlength)

第40页，共68页，2023年，2月20日，星期一具有n个记录的文件排序，必须做log2n

趟归并，每趟归并所花费的时间是O(n)二路归并排序算法的时间复杂度为T(n)=O(nlog2n)算法中增加了一个数组record，算法的辅助空间为S(n)=O(n)二路归并排序是稳定的算法评价第41页，共68页，2023年，2月20日，星期一Quicksort第42页，共68页，2023年，2月20日，星期一Quicksort(cont.)Divide:Partition(rearrange)thearrayA[p‥r]intotwosubarraysA[p‥q-1]andA[q+1‥r]suchthat：

eachelementofA[p‥q-1]<=A[q],inturn:A[q+1..r]>A[q]Conquer:SortthetwosubarraysA[p‥q-1]andA[q+1‥r]byrecursivecallstoquicksort.Combine:Sincethesubarraysaresortedinplace,noworkisneededtocombinethem:theentirearrayA[p‥r]isnowsorted.第43页，共68页，2023年，2月20日，星期一Quicksort(cont.)O(n)?第44页，共68页，2023年，2月20日，星期一分配排序分配排序是一种借助多关键码排序思想对单关键码排序的方法第45页，共68页，2023年，2月20日，星期一例子∶扑克牌排序要求:每张扑克牌具有两个属性∶花色（梅花<方块<红心<黑桃）和面值（2<3<…<10<J<Q<K<A），且花色的地位高于面值，排序后为∶梅花2，…，梅花A，方块2，…，方块A，红心2，…，红心A，黑桃2，…，黑桃A 分配排序例子第46页，共68页，2023年，2月20日，星期一扑克牌排序方法排序有以下两种方法∶第一是先将牌按花色分成4堆，然后将每堆按面值从小到大排序，最后按花色从小到大迭在一起第二种是先将牌按面值大小分成13堆，然后从小到大把它们收集起来，再按花色分成4堆，最后顺序地收集起来

第47页，共68页，2023年，2月20日，星期一对多关键码有序一般情况下，假设文件F有n个记录

F=(R0，R1，…Rn-1)且每个记录Ri中含有d个关键码(ki0,ki1,…,kid-1)，则文件对关键码(k0,k1,…,kd-1)有序是指∶文件中任意两个记录Ri和Rj(0≤i≤j≤n-1)满足词典次序有序关系

(ki0,ki1,…,kid-1)<(kj0,kj1,…,kjd-1)

其中k0称为最高位关键码，kd-1称为最低位关键码第48页，共68页，2023年，2月20日，星期一高位优先法:先对最高位关键码k0排序，将文件分成若干堆每堆中的记录都具有相同的k0然后分别就每堆对关键码k1排序，分成若干子堆，如此重复，直到对kd-1排序最后将各堆按次序叠在一起成为一个有序文件低位优先法:从最低位关键码kd-1起排序然后再对高一位关键码kd-2排序如此重复，直到对K0排序后便成为一个有序文件多关键码排序算法第49页，共68页，2023年，2月20日，星期一低位优先法比高位优先法简单，高位优先排序必须将文件逐层分割成若干子文件，然后各子文件独立排序低位优先排序不必分成子堆，对每个关键码都是整个文件参加排序，且可通过若干次“分配”和“收集”实现排序基数排序就是用低位优先法对单逻辑关键码排序的一种方法分配排序算法第50页，共68页，2023年，2月20日，星期一方法:把每个排序码看成是一个d元组∶

Ki=(Ki0,Ki1,…,Kid-1)其中每个Ki都是集合{C0，C1，…，Cr-1}(C0<C1<…<Cr-1)中的值即C0≤Kij≤Cr-1(0≤i≤n-1,0≤j≤d-1)其中r称为基数排序时先按Kid-1从小到大将记录分配到r个堆中然后依次收集，再按Kid-2分配到r个堆中如此反复，直到对Ki0分配、收集，得到的便是排好序的序列基数排序第51页，共68页，2023年，2月20日，星期一基数排序方法(续)基数排序时，为了实现记录的分配和收集，可以设r个队列，排序前为空队列，分配时将记录插入到各自的队列中，收集时将队列中的记录排在一起。第52页，共68页，2023年，2月20日，星期一初始序列为36，5，16，98，95，47，32，36’，48，10，请用基数排序法排序。

(1)初始状态

36→5→16→98→95→47→32→36’→48→10

例题第53页，共68页，2023年，2月20日，星期一54例题(续)(2)第一趟分配后

第54页，共68页，2023年，2月20日，星期一(3)第一趟收集后

10→32→5→95→36→16→36’→47→98→48(4)第二趟分配后 例题(续)第55页，共68页，2023年，2月20日，星期一例题(续)第56页，共68页，2023年，2月20日，星期一(5)第二趟收集后

5→10→16→32→36→36’→47’→48→95→98

例题(续)第57页，共68页，2023年，2月20日，星期一基数排序算法中，没有排序码的比较和记录的移动，只是对链表的扫描和指针的赋值，所以，时间耗费主要在修改指针上每趟排序中，清队列的时间为O(r)，将n个记录分配到队列的时间为O(n)，收集的时间为O(r)，因此，一趟排序的时间为O(r+n)总共要进行d趟排序，基数排序的时间复杂度是T(n)=O(d*(r+n))当n较大、d较小，特别是记录的信息量较大时，基数排序非常有效基数排序算法评价第58页，共68页，2023年，2月20日，星期一基数排序中，每个记录中增加了一个next字段，还增加了一个queue数组，故辅助空间为S(n)=O(n+r)基数排序是稳定的基数排序算法评价(续)第59页，共68页，2023年，2月20日，星期一Countingsort（8.2）第60页，共68页，2023年，2月20日，星期一COUNTING-SORT(A,B,k)1(for

i←0to

k)