第十章 内部排序.ppt

第十章内部排序,10.1 概述,10.2 插入排序,10.3 快速排序,10.4 选择排序,10.5 归并排序,10.6 基数排序,10.7 各种排序方法的综合比较,10.1 概 述,一、排序的定义,三、稳定排序和不稳定排序,五、内部排序方法的分类,四、内部排序和外部排序,二、排序的分类,一、什么是排序？,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52,49,80,36,14,58,61,23,97,75,调整为,14,23,36,49,52,58,61,75,80,97,一般情况下，假设含n个记录的序列为 R1,R2,，Rn 其相应的关键字序列为 K1,K2,，Kn,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为 Rp1,Rp2,，Rpn 的操作称作排序。,按待排序记录的稳定性-稳定排序-不稳定排序按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序,二、排序的分类,按排序所需工作量简单的排序方法：T(n)=O(n)先进的排序方法：T(n)=O(logn)基数排序：T(n)=O(d.n)-排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置待排序记录的存储方式地址连续的一组存储单元向量排序静态链表，记录间的次序由指针指示（链）表排序地址连续的一组存储单元，另设一个指示各个记录存储位置的地址向量地址排序,稳定与不稳定：一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。例：初始关键字：49，38，65，97，76，13，27，49排序结果：13，27，38，49，49，65，76，97 稳定的13，27，38，49，49，65，76，97 不稳定的,三、稳定排序和不稳定排序,四、内部排序和外部排序,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序。,五、内部排序的方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,ki,基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,基数类,待排记录的数据类型定义如下:,#define MAXSIZE 1000/待排顺序表最大长度,typedef int KeyType;/关键字类型为整数类型,typedef struct KeyType key;/关键字项 InfoType otherinfo;/其它数据项 RcdType;/记录类型,typedef struct RcdType rMAXSIZE+1;/r0闲置 int length;/顺序表长度 SqList;/顺序表类型,1.插入类,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,2.交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,3.选择类,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,4.归并类,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,5.基数类,借助多关键字排序的思想对单逻辑关键字进行排序的方法。,10.2 插 入 排 序,有序序列R1.i-1,Ri,无序序列 Ri.n,一趟直接插入排序的基本思想：,有序序列R1.i,无序序列 Ri+1.n,实现“一趟插入排序”可分三步进行：,3将Ri 插入(复制)到Rj+1的位置上。,2将Rj+1.i-1中的所有记录均后移 一个位置；,1在R1.i-1中查找Ri的插入位置，R1.j.key Ri.key Rj+1.i-1.key；,直接插入排序（基于顺序查找）,表插入排序（基于链表存储）,不同的具体实现方法导致不同的算法描述,折半插入排序（基于折半查找）,希尔排序（基于逐趟缩小增量）,一、直接插入排序,利用“顺序查找”实现“在R1.i-1中查找Ri的插入位置”,算法的实现要点：,从Ri-1起向前进行顺序查找，监视哨设置在R0；,R0=Ri;/设置“哨兵”,循环结束表明Ri的插入位置为 j+1,R0,j,Ri,for(j=i-1;R0.keyRj.key;-j);/从后往前找,j=i-1,插入位置,对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；,for(j=i-1;R0.keyRj.key;-j);Rj+1=Rj,R0,j,Ri,j=i-1,上述循环结束后可以直接进行“插入”,插入位置,令 i=2，3，,n,实现整个序列的排序。,for(i=2;i=n;+i)if(Ri.keyRi-1.key)在 R1.i-1中查找Ri的插入位置;插入Ri;,0 1 2 3 4 5 6 7 8,49,65 97 76 13 27 52,38,j=i-1,j,0 1 2 3 4 5 6 7 8,38 49,97 76 13 27 52,插入38,插入65,j=i-1,65,65,插入位置,插入52,0 1 2 3 4 5 6 7 8,12 27 38 49 65 76 97,52,j=i-1,j,插入位置,0 1 2 3 4 5 6 7 8,12 27 38 49 52 65 76 97,例如,例,49 38 65 97 76 13 27,i=2 38(38 49)65 97 76 13 27,i=3 65(38 49 65)97 76 13 27,i=4 97(38 49 65 97)76 13 27,i=5 76(38 49 65 76 97)13 27,i=6 13(13 38 49 65 76 97)27,i=1(),i=7(13 38 49 65 76 97)27,27,97,76,65,49,38,27,void InsertionSort(SqList+i)if(L.ri.key L.ri-1.key)/InsertSort,L.r0=L.ri;/复制为监视哨for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置,内部排序的时间分析：,实现内部排序的基本操作有两个：,（2）“移动”记录。,（1）“比较”序列中两个关键字的 大小；,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,平均情况下：即第i趟操作，插入记录大约同前面的i/2个记录进行关键码比较，移动记录的次数为i/2+2次。,由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法。,因为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。,二、折半插入排序,14 36 49 52 80,58 61 23 97 75,i,low,high,m,m,low,low,m,high,14 36 49 52 58 61 80,23 97 75,i,low,high,m,high,m,high,m,low,例如:,再如:,插入位置,插入位置,L.r,L.r,void BiInsertionSort(SqList&L)/BInsertSort,在 L.r1.i-1中折半查找插入位置；,for(i=2;i=L.length;+i)/for,L.r0=L.ri;/将 L.ri 暂存到 L.r0,for(j=i-1;j=high+1;-j)L.rj+1=L.rj;/记录后移,L.rhigh+1=L.r0;/插入,low=1;high=i-1;while(low=high),m=(low+high)/2;/折半,if(L.r0.key L.rm.key)high=m-1;/插入点在低半区else low=m+1;/插入点在高半区,三、表插入排序,为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上【P267-270】。,四、希尔排序（又称缩小增量排序）,基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列：R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d,希尔排序(缩小增量法)基本思想：不断把待排序列分割成若干个子序列，对每个子序列分别进行直接插入排序，待每个序列中的记录基本有序时，再对全体序列进行一次直接插入排序。在对序列进行分割时要保证后一次分割的序列数要少于前一次分割的序列数排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止,希尔排序-举例,#define T 3int d=5,3,1;,