第10章 排序

计算机科学与技术学院——数据结构第10章排序（Sort）目录§10.1排序概述§10.2插入排序§10.3交换排序§10.4选择排序§10.5归并排序§10.6基数排序计算机科学与技术学院——数据结构10.1排序概述1.操作对象：同类型数据元素的集合。2.操作目标：将数据元素的无序序列排列成按关键字值有序的序列。计算机科学与技术学院——数据结构3.稳定排序与非稳定排序：有：Ri.key==Rj.key假设排序前Ri的位置排列在Rj之前；经排序后若Ri的位置仍然排列在Rj之前，则是稳定排序算法；若不能保证这一点则是非稳定排序算法。•排序概述计算机科学与技术学院——数据结构4.内部排序与外部排序：内部排序----待排序的记录全部存放在内存;外部排序----一部分放在内存，一部分在外存。排序过程中存在着内、外存的数据交换。•排序概述计算机科学与技术学院——数据结构排序的基本动作：①比较②移动排序性能的评价：对比较次数和移动次数的评估•排序概述计算机科学与技术学院——数据结构第6页三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区计算机科学与技术学院——数据结构第7页基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法计算机科学与技术学院——数据结构第8页待排记录的数据类型定义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//顺序表类型计算机科学与技术学院——数据结构第9页1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。计算机科学与技术学院——数据结构第10页2.交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。计算机科学与技术学院——数据结构第11页3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。计算机科学与技术学院——数据结构第12页4.归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它方法计算机科学与技术学院——数据结构插入排序直接插入排序、折半插入排序、2路插入排序、希尔排序交换排序冒泡排序、快速排序选择排序简单选择排序、堆排序、树形选择排序归并排序2路归并排序基数排序•排序方法计算机科学与技术学院——数据结构先进排序算法：时间复杂度----O(nlogn)一般排序算法时间复杂度----O(n2)•排序方法计算机科学与技术学院——数据结构第10章排序（Sort）目录§10.1排序概述§10.2插入排序§10.3交换排序§10.4选择排序§10.5归并排序§10.6基数排序计算机科学与技术学院——数据结构10.2插入排序10.2.1直接插入排序10.2.2折半插入排序10.2.3二路插入排序10.2.4表插入排序10.2.5希尔排序计算机科学与技术学院——数据结构算法思想：排序区间R[1..n]；在排序的过程中，整个排序区间被分为两个子区间：有序区R[1..i-1]和无序区R[i..n]；共进行n－1趟排序，每趟排序都是把无序区的第一条记录Ri插到有序区的合适位置上。RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1nRR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n•直接插入排序计算机科学与技术学院——数据结构第18页有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]计算机科学与技术学院——数据结构第19页实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].keyR[j+1..i-1].key；计算机科学与技术学院——数据结构在具有n个元素的有序顺序表L[]中插入新元素e，使得L仍然有序：for(i=n-1;i=0&&L[i].keye.key;i--)L[i+1]=L[i];L[i+1]=e;RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1nRR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n•直接插入排序计算机科学与技术学院——数据结构初态：有序区为R[1]58154645900832R12345670监视哨•直接插入排序计算机科学与技术学院——数据结构1558R464590083212345670第一趟，i＝2；1558，15赋给监视哨；有序区中所有大于15的记录右移一位将15放入腾出的空位i=258154645900832R12345670初态：•直接插入排序计算机科学与技术学院——数据结构4658154645900832R12345670R4590083212345670第二趟，i＝3；4658，46赋给监视哨；有序区中所有大于46的记录右移一位将46放入腾出的空位i=3155815584645900832R12345670初态：第一趟后：•直接插入排序计算机科学与技术学院——数据结构R90083212345670第三趟，i＝4；4558，45赋给监视哨；有序区中所有大于45的记录右移一位将45放入腾出的空位i=41545584658154645900832R1234567015584645900832R1234567015465845900832R12345670初态：第一趟后：第二趟后：•直接插入排序计算机科学与技术学院——数据结构第四趟，i＝5；9058，没有移动发生；i=558154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567090154546580832R12345670初态：第一趟后：第二趟后：第三趟后：•直接插入排序计算机科学与技术学院——数据结构第五趟，i＝6；i=6R321234567008154546589058154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567015454658900832R12345670初态：第一趟后：第二趟后：第三趟后：第四趟后：•直接插入排序第六趟，i＝7；i=7R1234567008153245465858154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567015454658900832R1234567008154546589032R1234567090初态：第一趟后：第二趟后：第三趟后：第四趟后：第五趟后：计算机科学与技术学院——数据结构存储结构----以顺序存储结构为例#defineMAXSIZE200typedefstruct{//结点类型KeyTypekey;InfoTypeotherinfo;}RecordType;typedefstruct{//排序表类型RecordTypeR[MAXSIZE+1];intlength;}SqList;keyotherinfoR[]length•直接插入排序计算机科学与技术学院——数据结构直接插入排序利用“顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”算法的实现要点：计算机科学与技术学院——数据结构循环结束表明R[i]的插入位置为j+1从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”R[0]jR[i]for(j=i-1;R[0].keyR[j].key;--j);//从后往前找j=i-1插入位置计算机科学与技术学院——数据结构上述循环结束后可以直接进行“插入”对于在查找过程中找到的那些关键字不小于R[i].key的记录，在查找的同时实现记录向后移动；for(j=i-1;R[0].keyR[j].key;--j);R[j+1]=R[j]R[0]jR[i]j=i-1插入位置计算机科学与技术学院——数据结构令i=2，3，…,n,实现整个序列的排序。for(i=2;i=n;++i)if(R[i].keyR[i-1].key){在R[1..i-1]中查找R[i]的插入位置;插入R[i];}计算机科学与技术学院——数据结构voidInsertionSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i=L.length;++i)if(L.r[i].keyL.r[i-1].key){}}//InsertSortL.r[0]=L.r[i];//复制为监视哨for(j=i-1;L.r[0].keyL.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置R[0]有两个作用：1.保留R[i]的副本2.监视哨，监视j是否越界计算机科学与技术学院——数据结构最好的情况：表的初态恰好是正序排列比较次数：移动次数：Mmin＝0最坏的情况：表的初态恰好是逆序排列比较次数：移动次数：min211niCnmax2(2)(1)2ninnCimax2(4)(1)(1)2ninnMi•直接插入排序性能分析计算机科学与技术学院——数据结构等概率条件下平均情况：maxmin2CCC平均比较次数：maxmin2MMM平均移动次数：时间复杂度：O(n2)直接插入排序是一种稳定的排序方法•直接插入排序性能分析计算机科学与技术学院——数据结构10.2插入排序10.2.1直接插入排序10.2.2折半插入排序10.2.3二路插入排序10.2.4表插入排序10.2.5希尔排序计算机科学与技术学院——数据结构2020年1月23日星期四第38页因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。二、折半插入排序计算机科学与技术学院——数据结构2020年1月23日星期四第39页voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i=L.length;++i){}//forL.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]for(j=i-1;j=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入计算机科学与技术学院——数据结构low=1;high=i-1;while(low=high){}m=(low+high)/2;//折半if(L.r[0].keyL.r[m].key)high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区在L.r[1..i-1]中折半查找插入位置计算机科学与技术学院——数据结构2020年1月23日星期四第41页14364952805861239775ilowhighmmlowlowmhigh1436495