哲学C语言第十章课件

第10章内部排序学习目的与要求：1.深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;2.熟练掌握各种排序方法的执行过程；3.熟练掌握各种排序方法的时间复杂度的分析方法，从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能;4.理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。第10章内部排序学习目的与要求：1基本内容一、概述二、插入排序三、交换排序四、选择排序五、归并排序六、基数排序七、各种排序方法的比较基本内容一、概述2一、概述1．基本概念排序：将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。排序方法的稳定性：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的；反之，称该排序方法是不稳定的。内部排序：待排序记录存放在计算机的内存中进行的排序。一、概述1．基本概念排序：将数据元素(或记录)的一个任意序列3外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。排序的时间开销：排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的估算一般都按平均情况进行估算。对于那些受记录关键字序列初始排列及记录个数影响较大的，需要按最好情况和最坏情况进行估算。外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录42．排序的分类按排序过程依据的不同原则进行分类：交换排序选择排序归并排序计数排序插入排序按工作量进行分类：先进的排序方法，其时间复杂度为O(nlog2n)简单的排序方法,其时间复杂度为O(n2)基数排序基数排序，其时间复杂度为O(d·n)2．排序的分类按排序过程依据的不同原则进行分类：交换排序选择53．排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：（1）比较关键字的大小；（2）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方式：（1）记录存放在一组连续的存储单元中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。（2）记录存放在静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。——链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。——地址排序3．排序的基本操作和记录的存储方式排序过程中需要的两种基本操64．待排序记录的数据类型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RcdType;typedefstruct{RedTyper[MAXSIZE+1];//0单元作为哨兵intlength;}SqList;4．待排序记录的数据类型#defineMAXSIZE27二、插入排序1．直接插入排序2．折半插入排序3．2-路插入排序4．表插入排序5．希尔排序插入排序的基本方法是：每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。二、插入排序1．直接插入排序插入排序的基本方法是：每步将一个81．直接插入排序基本思想：当插入第i(i1)个记录时，前面的r[1],r[2]，…，r[i-1]已经排好序。这时，用r[i]的关键字与r[i-1]，r[i-2]，…的关键字顺序进行比较，找到插入位置即将r[i]插入，原来位置上之后的所有记录依次向后顺移。1．直接插入排序基本思想：9例49386597761327（）i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=7(133849657697)27j9727j76j65j49j38j排序结果：(13273849657697)例49386597710直接插入排序的算法voidInsertSort(SqList&L){//对待排序序列L进行直接插入排序for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=L.r[i];//复制为哨兵for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//记录插入}}//InsertSort直接插入排序的算法voidInsertSort(SqLi11算法评价记录的比较次数记录的移动次数最好情况最坏情况0时间复杂度：T(n)=O(n²)结论：空间复杂度：S(n)=O(1)直接插入排序是一个稳定的排序方法。算法评价记录的比较次数记录的移动次数最好情况最坏情况0时间复122．折半插入排序基本思想：利用直接插入排序的思想，只是在排序过程中，为减少查找次数，对已排好序的序列r[1],r[1],…,r[i-1]，利用折半查找法寻找r[i]的插入位置。例

(30)1370853942620i=213(1330)70853942620…...i=76(6133039427085)202．折半插入排序基本思想：例(30)13i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20l,m,hi=820(6133039427085)20lhi=820(613203039427085)i=820(6133014算法描述如下：voidBin_InsertSort(SqList&L){//对待排序序列L进行折半插入排序for(i=2;i<=L.length;++i){low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(r.[mid].key<=r[0].key)high=mid-1;elselow=mid+1;}for(j=i-1;j>h;j--)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//记录插入}}//Bin_InsertSort算法描述如下：voidBin_InsertSort(Sq15算法分析折半插入排序减少了关键字间的比较次数（由O(n²)下降到O(nlog2n))。折半插入排序的记录移动次数仍为O(n²)。折半插入排序的时间复杂度仍为O(n²)，空间复杂度仍为O(１)。折半插入排序是一个稳定的排序方法。算法分析折半插入排序减少了关键字间的比较次数（由O(n²)下163．2-路插入排序基本思想：利用直接插入排序的思想，只是在排序过程中，为减少记录的移动次数，但需要n个记录的辅助空间。其做法是：另设一个和L.r同类型的数组d，首先将L.r[1]赋给d.r[1]，并将d.r[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中第二个记录起依次到d.r[1]之前或之后的有序序列中。例

301370853942620排序过程中d的状态变化如下：i=1(30)firstfinali=2(30)13firstfinal3．2-路插入排序基本思想：利用直接插入排序的思想，只是在排17

301370853942620i=3(30)7013firstfinali=4(30)708513firstfinali=5(30)39708513firstfinali=6(30)3942708513firstfinali=7(30)39427085613firstfinali=8(30)3942708561320firstfinal3013708518算法描述如下：voidTwo_InsertSort(SqListL，SqList&D){//对待排序序列L进行2-路插入排序D.r[1]=L.r[1];D.length=L.length;first=final=1;for(i=2;i<=L.length;i++){x=L.r[i].key;if(x<D.r[1].key)if(first==1){D.r[D.length]=L.r[i];first=D.length;}else{low=first;high=D.length;while(low<=high){mid=(low+high)/2;if(x<D.r[mid].key)high=mid-1;elselow=mid+1;}算法描述如下：voidTwo_InsertSort(Sq19for(k=first;k<=high+1;k++)D.r[k-1]=D.r[k];D.r[high+1]=L.r[i];first--;}elseif(final==1){final++;D.r[final]=L.r[i];}else{low=2;high=final;while(low<=high){mid=(low+high)/2;if(x<D.r[mid].key)high=mid-1;elselow=mid+1;}for(k=fnal;k>=high+1;k++)D.r[k+1]=D.r[k];D.r[high+1]=L.r[i];fianl++;}}//for}//Two_InsertSortf20算法分析2-路插入排序减少了关键字间的比较次数(小于nlog2n)。2-路插入排序减少了记录移动次数，约为n2/8。2-路插入排序的时间复杂度仍为O(n²)，但空间复杂度为O(n)。2-路插入排序是一个稳定的排序方法。算法分析2-路插入排序减少了关键字间的比较次数(小于nlog214．表插入排序表插入排序采用了静态链表的存储结构，其排序过程如下：首先将静态链表中数组下标为1的分量（结点）和表头结点构成一个循环链表，然后依次将下标为2至n的分量（结点）按记录关键字非递减有序插入到循环链表中。表插入排序的基本操作仍是将一个记录插入到已排好序的有序表中。和直接插入排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂度仍是O(n2)。4．表插入排序表插入排序采用了静态链表的存储结构，其排序过程225．希尔排序希尔排序方法又称为“缩小增量”排序。基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。5．希尔排序希尔排序方法又称为“缩小增量”排序。基本思想：23例初始：4938659776132748554取d1=5一趟分组：49

38

65

97

76

13

27

48

55

4一趟排序：13

27

48

55

4

49

38

65

97

76取d2=3二趟分组：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d3=1三趟分组：1344838274955659776三趟排序：4132738484955657697例初始：4938659724希尔排序算法分析子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列；希尔排序可提高排序速度，因为关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序;增量序列取法有多种：1)没有除1以外的公因子2)最后一个增量值必须为1时间复杂度是所取增量序列的函数，但至今没人能够给出完整的数学分析。希尔排序是一个不稳定的排序方法。希尔排序算法分析子序列的构成不是简单的“逐段分割”，而是将相25三、交换排序1．起泡排序(BubbleSort)2．快速排序(QuickSort)三、交换排序1．起泡排序(BubbleSort)261．起泡排序(BubbleSort)基本过程：1)将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上;2)对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置;3)重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。1．起泡排序(BubbleSort)基本过程：27例：49383838381313384949491327276565651327383897761327494976132749

49132749

652749

76

49

97初始关键字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例：4938383828算法分析时间复杂度最好情况（正序）最坏情况（逆序）比较次数移动次数n-10T(n)=O(n²)空间复杂度：S(n)=O(1)起泡排序是一个稳定的排序方法算法分析时间复杂度最好情况（正序）最坏情况（逆序）比较次数移292．快速排序(QuickSort)对冒泡排序的一种改进基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行排序，以达到整个序列有序。2．快速排序(QuickSort)对冒泡排序的一种改进基本30排序过程：1)初始时令i=s,j=t;2)首先从j所指位置向前搜索第一个关键字小于pivot的记录，并和rp交换;3)再从i所指位置起向后搜索，找到第一个关键字大于pivot的记录，和rp交换;4)重复上述两步，直至i==j为止;（此时整个序列被分成有序的前后两块）5)再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，pivot=rp.key排序过程：1)初始时令i=s,j=t;对31快速排序举例初始关键字：{49，38，65，97，76，13，27，49}pivotkey491次交换后：{27，38，65，97，76，13，，49}ijijji2次交换后：{27，38，，97，76，13，65，49}ijj3次交换后：{27，38，13，97，76，，65，49}iji4次交换后：{27，38，13，，76，97，65，49}jij一趟完成后：{27，38，13，49，76，97，65，49}快速排序举例初始关键字：{49，38，65，97，76，1332一趟完成后：{27，38，13，49，76，97，65，49}分别进行快速排序：{13

27

3849

4965

76

97}快速排序结束：{13

27

3849

49

65

76

97}一趟完成后：{27，38，13，49，76，97，65，4933快速排序算法描述：intPartition(SqList&L,intlow,inthigh){//对顺序表L进行一趟快速排序，返回枢轴记录所在的位置

L.r[0]=L.r[low];//用子表的第一记录作枢轴记录pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比pivotkey小的记录移到低端while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//将比pivotkey大的记录移到高端}L.r[low]=l.r[0];returnlow;}快速排序算法描述：intPartition(SqList34voidQsort(SqList&L,intlow,inthigh){//对顺序表L的子序列L.r[low..high]作快速排序if(low<high){pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);}}//QSortvoidQuickSort(SqList&L){//对顺序表L作快速排序Qsort(L,1,L.length);}//QuickSortvoidQsort(SqList&L,intlow35快速排序算法分析在n个元素的序列中，对一个记录定位所需时间为O(n)。若设T(n)是对n个元素的序列进行排序所需的时间，而且每次对一个记录正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：T(n)

cn+2T(n/2) //c是一个常数

cn+2(cn/2+2T(n/4))=2cn+4T(n/4)2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)………

cn

log2n+nT(1)=O(nlog2n)快速排序的平均时间是O(nlogn)，在所有同数量级(O(nlogn))的排序方法中，就平均计算时间而言，快速排序是我们所讨论的所有内部排序方法中最好的一个。快速排序算法分析在n个元素的序列中，对一个记录定位所需时间为36快速排序需要一个栈空间来实现递归，若每趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为O(logn)。若初始序列按关键字基本有序（最坏情况），快速排序蜕化为起泡排序，其时间复杂度为O(n2)，最坏情况下栈的深度为n。改进的方法，用“三者取中”的法则选取枢轴记录（pivotkey)。快速排序是一种不稳定的排序方法。对于n较大的平均情况而言，快速排序是“快速”的，但是当n很小时，这种排序方法往往比其它简单排序方法还要慢。快速排序需要一个栈空间来实现递归，若每趟排序都将记录序列均匀37四、选择排序基本思想：每一趟(例如第i趟，i=1,…,n-1)在n-i+1

个记录中选取关键字最小的记录作为有序序列中第i个记录。1．简单选择排序(SelectSort)2．树形选择排序(TreeSelectionSort)3．堆排序(HeapSort)四、选择排序基本思想：每一趟(例如第i趟，i=1,381．简单选择排序(SelectSort)基本步骤：i从1开始，直到n-1，进行n-1趟排序，第i趟的排序过程为：在一组记录r[i]～r[n](i=1,2,…,n-1)中选择具有最小关键字的记录,并和第i个记录进行交换。1．简单选择排序(SelectSort)基本步骤：39简单选择排序的算法voidSelectSort(SqList&L){//对顺序表L进行简单选择排序for(i=1;i<L.length;++i){k=i;//选择关键字最小的记录for(j=i+1;j<=L.length;++j) if(L.r[k].key>L.r[j].key)k=j;

//最小记录与第i个记录互换if(i!=k){temp=L.r[i]; L.r[i]=L.r[k];L.r[k]=temp;}}}简单选择排序的算法40算法分析简单选择排序的关键字比较次数与记录的初始排列无关。第i趟选择具有最小关键字的记录所需的比较次数是n-i次，若整个待排序序列有n条记录。因此，总的关键字比较次数为：记录的移动次数与记录的初始排列有关。当初始状态是按其关键字从小到大有序的时候，记录的移动次数为0，达到最少(最好情况)。最坏情况是每一趟都要进行交换，总的记录移动次数为3(n-1)。简单选择排序是一种不稳定的排序方法。简单选择排序的时间复杂度是O(n2)，空间复杂度是O(1)。算法分析简单选择排序的关键字比较次数与记录的初始排列无关。第412．树形选择排序(TreeSelectionSort)又称锦标赛排序(TournamentSort),是简单选择排序的改进(减少关键字间的比较次数)。基本思想:与体育比赛时的淘汰赛类似。首先取得n个记录的关键字，进行两两比较，得到n/2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这n/2个记录再进行关键字的两两比较，…，如此重复，直到选出一个关键字最小的记录为止。2．树形选择排序(TreeSelectionSort)42如果n不是2的k次幂，则让叶子结点数补足到满足2k-1个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放记录的关键字key外，还存放了此记录是否要参选的标志flag和此记录在满二叉树中的序号index。如果n不是2的k次幂，则让叶子结点数补足到满足2k43形成初始胜者树（最小关键字上升到根）关键字比较次数:7形成初始胜者树（最小关键字上升到根）关键字比较次数:744关键字比较次数:2关键字比较次数:2关键字比较次数:2关键字比较次数:245说明：锦标赛排序构成的树是完全二叉树，其深度为log2n

+1，其中n为待排序元素个数。除第一次选择具有最小关键字的记录需要进行n-1次关键字比较外，重构胜者树选择具有次小、再次小关键字记录所需的关键字比较次数均为log2n。总关键字比较次数为O(nlog2n)。记录的移动次数不超过关键字的比较次数，所以锦标赛排序总的时间复杂度为O(nlog2n)。这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。锦标赛排序是一个稳定的排序方法。说明：锦标赛排序构成的树是完全二叉树，其深度为log2n463．堆排序(HeapSort)堆排序是树形选择排序的一种改进，主要是为了减少辅助存储空间和多余比较。堆的定义：

n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系时，称之为堆。3．堆排序(HeapSort)堆排序是树形47例：（96，83，27，38，11，9）例：（13，38，27，50，76，65，49，97）可将堆序列看成完全二叉树大顶堆小顶堆例：（96，83，27，38，11，9）例：（13，3848堆排序的基本思想是：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分两步处理：第一步：初建堆。从堆的定义出发，当i=1,2,…,n/2时应满足ki≤k2i和ki≤k2i+1（或ki≥k2i和ki≥k2i+1）。所以先取i=n/2(它一定是第n个结点双亲的编号)将以i结点为根的子树调整为堆；然后令i=i-1，再将以i结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。第二步：堆排序。首先输出堆顶元素，让堆中最后一个元素上移到原堆顶位置，然后恢复堆，因为经过上移堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤，直到全部元素输出完为止。我们称这个从堆顶至叶子的调整过程为“筛选”。从一个无序序列建堆的过程就是一个反复“筛选”的过程。堆排序的基本思想是：把n个记录存于向量r之中，把它看成完全二49例如：根据输入序列{49,38,65,97,76,13,27,49}，建立一个小顶堆。第一步：初建堆例如：根据输入序列{49,38,65,97,76,50第二步：堆排序。这是一个反复输出堆顶元素，将堆尾元素移至堆顶，再调整恢复堆的过程。恢复堆的过程与初建堆中i=1时所进行的操作完全相同。注意：每输出一次堆顶元素，堆顶与堆尾元素就交换一次，同时堆尾的逻辑位置退1，直到堆中剩下一个元素为止。第二步：堆排序。这是一个反复输出堆顶元素，将堆尾元素移至堆顶51例如：对于给定的输入序列{80,42,13,55,94,17,46}，进行堆排序。例如：对于给定的输入序列{80,42,13,55,952[哲学]C语言第十章课件53堆排序算法描述如下：voidHeapSort(HeapType&H){//对顺序表H进行堆排序

//初始堆建立

for(i=H.length/2;i>0;--i)HeapAdjust(H,i,H.length);

//堆的输出与调整

for(i=H.length;i>1;--i){temp=H.r[1];H.r[1]=H.r[i];H.r[i]=temp;HeapAdjust(H,1,i-1);}}堆排序算法描述如下：voidHeapSort(HeapTy54voidHeapAdjust(HeapType&H,ints,intm){//调整H.r[s..m]成一个大顶堆rc=H.r[s];for(j=2*s;j<=m;j*=2){if(j<m&&H.r[j].key<H.r[j+1].key)j++;if(rc.key≥H.r[j.key])break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}voidHeapAdjust(HeapType&H,i55算法分析时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：S(n)=O(1)对记录数较少的文件不值得提倡，但对n较大的文件很有效。堆排序是一个不稳定的排序方法。算法分析时间复杂度：最坏情况下T(n)=O(nlogn)空间56五、归并排序(MergingSort)归并排序(mergesort)是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、2-路归并排序；可用于内部排序，也可以用于外部排序。我们仅对内部排序的2-路归并方法进行讨论。2-路归并排序算法思路：(1)把n个记录看成n个长度为1的有序子表；(2)进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表；(3)重复第(2)步直到所有记录归并成一个长度为n的有序表为止。五、归并排序(MergingSort)归并57例如：初始关键字：[49][38][65][97][76][13][27]一趟归并之后：[3849][6597][1376][27]两趟归并之后：[38496597][132776]三趟归并之后：[13273849657697]例如：一趟归并之后：[3849][582-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，其算法描述如下：voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]j=m+1;k=i;while(i<=m&&j<=n)if(SR[i].key<=SR[j].key)TR[k++]=SR[i++];elseTR[k++]=SR[j++];while(i<=m)TR[k++]=SR[i++];while(j<=n)TR[k++]=SR[j++];}//Merge2-路归并排序中的核心操作是将一维数组中前后592-路归并排序的递归算法描述如下：voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){//将SR[s..t]归并排序为TR1[s..t]。if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]MSort(SR,TR2,s,m);//将SR[s..m]归并为有序的TR2[s..m]

MSort(SR,TR2,m+1,t);//将SR[m+1..t]归并为有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]

}}//MSortvoidMergeSort(SqList&L){//对顺序表L作归并排序MSort(L.r,L.r,1,L.length);}//MergeSort2-路归并排序的递归算法描述如下：voidMSort(R60算法分析在归并排序算法中，递归深度为O(log2n)，记录的关键字比较次数为O(nlog2n)。算法总的时间复杂度为O(nlog2n)。归并排序所需的附助空间较多，需要一个与原待排序序列数组同样大小的辅助数组，所以算法的空间复杂度为O(n)。归并排序是一个稳定的排序方法。算法分析在归并排序算法中，递归深度为O(log2n)，记录的61六、基数排序(RadixSort)基数排序是与前面所介绍的排序方法完全不同的一种排序方法，该排序方法采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。多关键字排序以扑克牌排序为例：每张扑克牌有两个“关键字”：花色和面值。其有序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A注：“花色”的地位高于“面值”如果我们进行多关键字排序,可以把所有扑克牌排成以下次序：2,…,A,2,…,A,2,…,A,2,…,A六、基数排序(RadixSort)基数排序62对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序（先按不同“面值”分成13堆，然后将这13堆牌自小至大叠在一起（大数放在小数的下面），然后将这付牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌按自小至大的次序合在一起）。一般情况下，假定有一个n个记录的序列{R1,R2,…,Rn}，且每个记录Ri中含有d个关键字

(Ki0,Ki1,…,Kid-1).如果对于序列中任意两个记录Ri

和Rj

(1

i<j

n)都满足：

(Ki0,Ki1,…,Kid-1)<

(Kj0,Kj1,…,Kjd-1)

则称序列{R1,R2,…,Rn}对关键字(K0,K1,…,Kd-1)有序。其中，K0称为最主位关键字，Kd-1称为最次位关键字。对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；63实现多关键字排序通常有两种方法：最高位优先MSD(MostSignificantDigitfirst)最低位优先LSD(LeastSignificantDigitfirst)最高位优先法先根据最主位关键字K0排序,得到若干子序列，每个子序列中每个记录都有相同关键字K0。再分别对每个子序列中记录根据关键字K1进行排序，按K1值的不同，再分成若干个更小的子序列，每个子序列中的记录具有相同的K0和K1值。依此重复，直到对关键字Kd-1完成排序为止。最后，把所有子序列中的记录依次连接起来，就得到一个有序的记录序列。实现多关键字排序通常有两种方法：最高位优先法64最低位优先法首先依据最次位关键字Kd-1对所有记录进行一趟排序，再依据关键字Kd-2对上一趟排序的结果再排序，依次重复，直到依据关键字K0最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键字进行排序时，不需要再分组，而是整个序列都参加排序。MSD和LSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki

看作是一个子关键字组：(Ki0,Ki1,…,Kid-1)最低位优先法MSD和LSD方法也可应用于对65链式基数排序基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键字进行排序。在这种方法中，把单关键字Ki

看成是一个d元组：

(Ki0,Ki1,…,Kid-1)

其中的每一个分量Kij

(0

jd-1)也可看成是一个关键字。假设分量Kij

有radix种取值，则称radix为基数。例如，关键字984可以看成是一个3元组(9,8,4)，每一位有0,1,…,9等10种取值，基数radix=10。关键字‘data’可以看成是一个4元组(d,a,t,a)，每一位有‘a’,‘b’,…,‘z’等26种取值，radix=26。链式基数排序基数排序是典型的LSD排序方法，66针对d元组中的每一个分量Kij，把记录序列中的所有记录,按Kij的取值，先“分配”到radix(rd)个队列中去。然后再按各队列的顺序，依次把记录从队列中“收集”起来，这样所有记录按取值Kij排序完成。如果对于所有记录的关键字K0,K1,…,Kn-1，依次对各位的分量，让j=d-1,d-2,…,0，分别用这种“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集”完成后，所有记录就按其关键字的值从小到大排好序了。各队列采用链式存储结构，分配到同一队列的关键字用链接指针链接起来。每一队列设置两个队列指针：

front[radix]指示队头，rear[radix]

指向队尾。以静态链表作为待排序序列的存储结构。在记录重排时不必移动记录，只需修改各记录的链接指针即可。针对d元组中的每一个分量Kij，把记录序列中67例如：待排序序列放在单链表中，如下所示：109063930589184505269008083278e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]278109063930589184505269008083第一趟分配063083184505278008109589269930第一趟收集例如：待排序序列放在单链表中，如下所示：109063930568063083184505278008109589269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]930063083184505278008109589269第二趟分配008109930063269278083184589505第二趟收集06308318450527800810958926993069008109930063269278083184589505e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]505008109930063269278083184589第三趟分配063083109184269278505589930008第三趟收集后的有序序列00810993006326927808318458950570算法分析若每个关键字有d位，需要重复执行d趟“分配”与“收集”。每趟对n个记录进行“分配”的时间复杂度为O(n)，对rd(rd是指每个关键字的取值范围)个队列进行

“收集”的时间复杂度为O(rd)。总时间复杂度为O(d(n+rd))。基数排序需要增加n+2rd个附加链接指针。基数排序是稳定的排序方法。算法分析若每个关键字有d位，需要重复执行d趟“分配”与“71七、各种排序方法的比较辅助空间最差最好稳定性比较次数移动次数最差最差最好最好直接插入排序希尔排序起泡排序快速排序简单选择排序堆排序归并排序基数排序排序方法O(n)O(n2)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(n)O(n2)O(n2)O(n2)O(n2)O(nlog2n)O(nlog2n)0O(n2)O(n2)O(n2)00O(n)稳定不稳定O(nlog2n)O(nlog2n)稳定不稳定不稳定不稳定稳定稳定O(1)O(1)O(1)O(1)O(1)O(1)O(log2n)O(n)O(1)O(1)O(1)O(1)O(n)O(n)O(rd)O(rd)//////0000七、各种排序方法的比较辅助空间最差最好稳定性比较次数移动次数72说明：直接插入排序、折半插入排序、冒泡排序、锦标赛排序、归并排序、基数排序是稳定的排序方法；而希尔排序、快速排序、简单选择排序、堆排序是不稳定的排序方法。直接插入排序、冒泡排序、简单选择排序是简单的排序方法，其时间复杂度都为O(n2)，空间复杂度为O(1)。快速排序、锦标赛排序、堆排序和归并排序是先进型的排序方法，其时间复杂度均为O(nlog2n)，空间复杂度分别为O(log2n)、O(n)、O(1)、O(n)。希尔排序又称为缩小增量的排序，也是插入类排序的方法，但在时间上有较大的改进。其时间复杂度约为O(n1.3),空间复杂度为O(1)。说明：直接插入排序、折半插入排序、冒泡排序、锦标赛排序、归并73就平均时间性能而言，快速排序最佳，但最坏情况下的时间性能不如堆排序和归并排序。当在n个数据（n很大）中选出最小的几个数据时，堆排序最快。归并排序对待排序关键字的初始排列不敏感，故排序速度较稳定。但所需辅助空间较多（O(n)）。各种不同的排序方法应根据不同的环境及条件分别选择。一般而言，对于排序元素少的，可以选用时间复杂度为O(n2)的算法；对于元素多的，可选用时间复杂度为O(nlog2n)的算法。简单排序以“直接插入排序”最简单，当序列“基本有序”或n较小时，它是最佳排序方法，通常用它与先进的排序方法诸如快速排序等结合使用。基数排序最适合n很大而关键字较小的序列。就平均时间性能而言，快速排序最佳，但最坏情况下的时间性能不如74第10章内部排序学习目的与要求：1.深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;2.熟练掌握各种排序方法的执行过程；3.熟练掌握各种排序方法的时间复杂度的分析方法，从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能;4.理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。第10章内部排序学习目的与要求：75基本内容一、概述二、插入排序三、交换排序四、选择排序五、归并排序六、基数排序七、各种排序方法的比较基本内容一、概述76一、概述1．基本概念排序：将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。排序方法的稳定性：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的；反之，称该排序方法是不稳定的。内部排序：待排序记录存放在计算机的内存中进行的排序。一、概述1．基本概念排序：将数据元素(或记录)的一个任意序列77外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。排序的时间开销：排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的估算一般都按平均情况进行估算。对于那些受记录关键字序列初始排列及记录个数影响较大的，需要按最好情况和最坏情况进行估算。外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录782．排序的分类按排序过程依据的不同原则进行分类：交换排序选择排序归并排序计数排序插入排序按工作量进行分类：先进的排序方法，其时间复杂度为O(nlog2n)简单的排序方法,其时间复杂度为O(n2)基数排序基数排序，其时间复杂度为O(d·n)2．排序的分类按排序过程依据的不同原则进行分类：交换排序选择793．排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：（1）比较关键字的大小；（2）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方式：（1）记录存放在一组连续的存储单元中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。（2）记录存放在静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。——链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。——地址排序3．排序的基本操作和记录的存储方式排序过程中需要的两种基本操804．待排序记录的数据类型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RcdType;typedefstruct{RedTyper[MAXSIZE+1];//0单元作为哨兵intlength;}SqList;4．待排序记录的数据类型#defineMAXSIZE281二、插入排序1．直接插入排序2．折半插入排序3．2-路插入排序4．表插入排序5．希尔排序插入排序的基本方法是：每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。二、插入排序1．直接插入排序插入排序的基本方法是：每步将一个821．直接插入排序基本思想：当插入第i(i1)个记录时，前面的r[1],r[2]，…，r[i-1]已经排好序。这时，用r[i]的关键字与r[i-1]，r[i-2]，…的关键字顺序进行比较，找到插入位置即将r[i]插入，原来位置上之后的所有记录依次向后顺移。1．直接插入排序基本思想：83例49386597761327（）i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=7(133849657697)27j9727j76j65j49j38j排序结果：(13273849657697)例49386597784直接插入排序的算法voidInsertSort(SqList&L){//对待排序序列L进行直接插入排序for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=L.r[i];//复制为哨兵for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//记录插入}}//InsertSort直接插入排序的算法voidInsertSort(SqLi85算法评价记录的比较次数记录的移动次数最好情况最坏情况0时间复杂度：T(n)=O(n²)结论：空间复杂度：S(n)=O(1)直接插入排序是一个稳定的排序方法。算法评价记录的比较次数记录的移动次数最好情况最坏情况0时间复862．折半插入排序基本思想：利用直接插入排序的思想，只是在排序过程中，为减少查找次数，对已排好序的序列r[1],r[1],…,r[i-1]，利用折半查找法寻找r[i]的插入位置。例

(30)1370853942620i=213(1330)70853942620…...i=76(6133039427085)202．折半插入排序基本思想：例(30)87i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20l,m,hi=820(6133039427085)20lhi=820(613203039427085)i=820(6133088算法描述如下：voidBin_InsertSort(SqList&L){//对待排序序列L进行折半插入排序for(i=2;i<=L.length;++i){low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(r.[mid].key<=r[0].key)high=mid-1;elselow=mid+1;}for(j=i-1;j>h;j--)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//记录插入}}//Bin_InsertSort算法描述如下：voidBin_InsertSort(Sq89算法分析折半插入排序减少了关键字间的比较次数（由O(n²)下降到O(nlog2n))。折半插入排序的记录移动次数仍为O(n²)。折半插入排序的时间复杂度仍为O(n²)，空间复杂度仍为O(１)。折半插入排序是一个稳定的排序方法。算法分析折半插入排序减少了关键字间的比较次数（由O(n²)下903．2-路插入排序基本思想：利用直接插入排序的思想，只是在排序过程中，为减少记录的移动次数，但需要n个记录的辅助空间。其做法是：另设一个和L.r同类型的数组d，首先将L.r[1]赋给d.r[1]，并将d.r[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中第二个记录起依次到d.r[1]之前或之后的有序序列中。例

301370853942620排序过程中d的状态变化如下：i=1(30)firstfinali=2(30)13firstfinal