数据结构课件-第九章.ppt

第九章 内部排序,9.1 排序的基本概念,9.2 插入类排序,9.3 交换类排序法,9.4 选择类排序法,9.5 归并排序,9.6 分配类排序,9.7 各种排序方法的综合比较,返回主目录,9.1 排序的基本概念,排序：有n个记录的序列R1，R2，Rn，其相应关键字的序列是K1，K2，Kn，相应的下标序列为1，2，n。通过排序，要求找出当前下标序列1，2，n的一种排列p1，p2，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1 Kp2 Kpn，这样就得到一个按关键字有序的记录序列：Rp1，Rp2，Rpn。,返回主目录,内部排序：整个排序过程完全在内存中进行，称为内部排序。,外部排序：由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。,稳定排序和不稳定排序：假设Ki=Kj(1in，1jn，ij)，若在排序前的序列中Ri领先于Rj(即ij)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，当相同关键字的领先关系在排序过程中发生变化者，则称所用的排序方法是不稳定的。,返回主目录,在排序过程中，一般进行两种基本操作：,（1）比较两个关键字的大小；（2）将记录从一个位置移动到另一个位置。,对于第二种操作，需要采用适当地存储方式，即向量结构、链表结构以及记录向量与地址向量结合的表示方法。,我们重点来讨论在向量存储结构上各种排序方法的实现。,返回主目录,9.2 插入类排序,基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。,9.2.1 直接插入排序,基本操作是将第i个记录插入到前面i-1个已排好序的记录中，具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。,返回主目录,48 62 35 77 55 14 35 98 48 62 35 77 55 14 35 98 35 48 62 77 55 14 35 98 35 48 62 77 55 14 35 98 35 48 55 62 77 14 35 98 14 35 48 55 62 77 35 98 14 35 35 48 55 62 77 98 14 35 35 48 55 62 77 98,下面给出了一个完整的直接插入排序实例。图中大括号内为当前已排好序的记录子集合。,返回主目录,假设待排序记录存放在r1.n之中，为了提高效率，我们附设一个监视哨r0，使得r0始终存放待插入的记录。,void InsSort(RecordType r,int length)/*对记录数组r做直接插入排序，length为数组的长度*/for(i=2;i length;i+)r0=ri;j=i-1;/*将待插入记录存放到r0中*/while(r0.key rj.key)/*寻找插入位置*/rj+1=rj;j=j-1;rj+1=r0;/*将待插入记录插入到已排序的序列中*/*InsSort*/,直接插入排序算法,返回主目录,该算法的要点是：使用监视哨r0临时保存待插入的记录。从后往前查找应插入的位置。查找与移动用同一循环完成。,直接插入排序算法分析：,从空间角度来看，它只需要一个辅助空间r0。从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。,直接插入排序方法是稳定的排序方法。,返回主目录,9.2.2 折半插入排序,void BinSort(RecordType r,int length)/*对记录数组r进行折半插入排序，length为数组的长度*/for(i=2;i=low;-j)rj+1=rj;/*记录依次向后移动*/rlow=x;/*插入记录*/,返回主目录,采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第i个元素时，设i=2j,则需进行log2i次比较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。,算法分析：,返回主目录,9.2.3 表插入排序,表插入排序是采用链表存储结构进行插入排序的方法。表插入排序的基本思想是：先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表。,typedef int KeyType;typedef struct KeyType key;OtherType other_data;int next;RecordType1;,类型说明如下：,返回主目录,void SLinkListSort(RecordType1 r,int length)int n=length;r0.next=n;rn.next=0;for(i=n-1;i=1;-i)p=r0.next；q=0;while(p0/*修改指针，完成插入*/*SLinkListSort*/,表插入排序算法,返回主目录,算法分析：,每插入一条记录，最大的比较次数等于已排好序的记录个数，即当前循环链表长度。总的比较次数为：,因此表插入排序的时间复杂度为T(n)=O(n2)。,返回主目录,9.4 选择类排序法,选择排序的基本思想是：每一趟在n-i+1（i=1，2，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。,9.4.1 简单选择排序,基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。,选择排序示例见P240的图9.5所示。,返回主目录,简单选择排序的算法描述如下：,void SelectSort(RecordType r,int length)/*对记录数组r做简单选择排序，length为数组的长度*/n=length;for(i=1;i=n;+i)k=i；for(j=i+1;j=n;+j)if(rj.key rk.key)k=j；if(k!=i)x=ri；ri=rk；rk=x;/*SelectSort*/,返回主目录,简单选择排序算法分析：,在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。进行比较操作的时间复杂度为O(n2)。,返回主目录,9.4.2 树型选择排序,树型选择排序也称作锦标赛排序。它的基本思想是：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在 n/2 个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。,例如p241的图9.6所示的树型选择排序,返回主目录,在树型选择排序中，被选中的关键字都是走了一条由叶子结点到根结点的比较的过程,由于含有n个叶子节点的完全二叉数的深度为log2n+1，则在树型选择排序中，每选择一个小关键字需要进行log2n次比较，因此其时间复杂度为O(nlog2n)。移动记录次数不超过比较次数，故总的算法时间复杂度为O(nlog2n)。,算法分析：,返回主目录,9.4.3 堆排序,堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记录大小的辅助空间。堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析而已。,返回主目录,具体做法：,把待排序的记录的关键字存放在数组r1.n之中，将r 看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r1作为二叉树的根，以下各记录r2.n依次逐层从左到右顺序排列，任意结点ri的左孩子是r2i,右孩子是r2i+1,双亲是ri/2。对这棵完全二叉树进行调整，使各结点的关键字值满足下列条件：ri.keyr2i.key并且ri.keyr2i+1.key(i=1,2,.n/2)，满足这个条件的完全二叉树为堆。,返回主目录,堆中根结点的关键字最大，称为大根堆。反之，如果这棵完全二叉树中任意结点的关键字大于或者等于其左孩子和右孩子的关键字（当有左孩子或右孩子时），对应的堆为小根堆。,一个大根堆和一个小根堆的示例见p242的图9.7所示。,返回主目录,堆排序堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆,例（96，83，27，38，11，9）,例（13，38，27，50，76，65，49，97）,可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值,堆排序的过程主要需要解决两个问题：(1)按堆定义建初堆（2）去掉最大元之后重建堆，得到次大元。,问题1:当堆顶元素改变时，如何重建堆?,首先将完全二叉树根结点中的记录移出，该记录称为待调整记录。此时根结点相当于空结点。从空结点的左、右子中选出一个关键字较小的记录，如果该记录的关键字小于待调整记录的关键字，则将该记录上移至空结点中。此时，原来那个关键字较小的子结点相当于空结点。重复上述移动过程，直到空结点左、右子的关键字均不小于待调整记录的关键字。此时，将待调整记录放入空结点即可。上述调整方法相当于把待调整记录逐步向下“筛”的过程，所以一般称为“筛选”法。,返回主目录,例,筛选过程示例见p316的图9.8所示。,筛选算法为：,void sift（RecordType r,int，int）/*假设k.m是以k为根的完全二叉树，且分别以2k和2k+1为根的左、右子树为大根堆，调整rk，使整个序列rk.m满足堆的性质*/t=rk；/*暂存“根”记录rk*/x=rk.key；i=k；j=2*i；finished=FALSE；while(j=m&!finished)if(jm&rj.key rj+1.key)j=j+1；/*若存在右子树，且右子树根的关键字大，则沿右分支“筛选”*/,返回主目录,if(x=rj.key)finished=TRUE；/*筛选完毕*/else ri=rj；i=j；j=2*i；/*继续筛选*/ri=t;/*rk填入到恰当的位置*/*sift*/,返回主目录,问题2:如何由一个任意序列建初堆？,一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆，因而可以反复利用“筛选”法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆。,建堆算法如下：,void crt_heap(RecordType r,int length)/*对记录数组r建堆，length为数组的长度*/n=length;for(i=n/2;i=1;-i)/*自第个记录开始进行筛选建堆*/sift(r，i，n)；,返回主目录,例如，已知关键字序列：48，62，35，77，55，14，35，98，要求将其筛选为一个堆。在此，n=8，所以应从第个结点77开始筛选。从无序序列的第n/2个元素,即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止.建堆过程见P317的图9.9。图中箭头所指为当前待筛结点。,返回主目录,例 含8个元素的无序序列（49，38，65，97，76，13，27，50）,问题3:如何利用堆进行排序？,进行堆排序的步骤：将待排序记录按照堆的定义建初堆（算法9.10），并输出堆顶元素；调整剩余的记录序列，利用筛选法将前n-i个元素重新筛选建成为一个新堆，再输出堆顶元素；重复执行步骤n-1次进行筛选,新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多，最后使待排序记录序列成为一个有序的序列，这个过程称之为堆排序。,完整的堆排序过程见p246的图9.10,图中箭头所指为当前堆尾结点。,返回主目录,堆排序的算法为：,void HeapSort（RecordType r,int length）/*对r1.n进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列*/crt_heap（r,length）；n=length;for(i=n;i=2;-i)b=r1;/*将堆顶记录和堆中的最后一个记录互换*/r1=ri ri=b;sift(r，1，i-1)；/*进行调整，使r1.i-1变成堆*/*HeapSort*/,返回主目录,堆排序算法分析：,堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。对深度为k的堆，筛选算法中进行的关键字的比较次数至多为2（k-1）次，则在建含n个元素、深度为h的堆时，总共进行的关键字比较次数不超过4n。另外，n个结点的完全二叉树的深度为：log2n+1，则调整建新堆时调用sift过程n-1次总共进行的比较次数不超过：,2(log2(n-1)+log2(n-2)+log22 2n log2n,因此，堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。,堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。,返回主目录,9.5 归并排序,基本思想是将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。,返回主目录,归并排序的示例为：,返回主目录,2-路归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列。,合并算法描述如下：,void Merge(RecordType r1,int low,int mid,int high,RecordType r)/*已知r1low.mid和r1mid+1.high分别按关键字有序排列，将它们合并成一个有序序列，存放在rlow.high*/i=low；j=mid+1；k=low；while(i=mid)&(j=high)if(r1i.key=r1j.key)rk=r1i；+i；else rk=r1j；+j；+k；,返回主目录,if(i=mid)rk.high=r1i.mid；if(j=high)rk.high=r1j.high；/*Merge*/,返回主目录,2-路归并排序可以采用递归方法实现，具体描述如下：,void MergeSort(RecordType r1,int low,int high,RecordType r)/*r1low.high经过排序后放在rlow.high中，r2low.high为辅助空间*/RecordType*r2；r2=(RecordType*)malloc(sizeof(RecordType)*(hight-low+1);if(low=high)rlow=r1low；elsemid=(low+high)/2；MergeSort(r1，low，mid,r2)；MergeSort(r1，mid+1，high,r2)；Merge(r2，low，mid，high，r)；free(r2);/*MergeSort*/,返回主目录,归并排序的算法分析：,归并排序中一趟归并中要多次用到2-路归并算法，一趟归并排序的操作是调用 n/2h 次算法merge 将r11n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在r1n中，其 时间复杂度为O(n)。整个归并排序需进行m（m=log2n）趟2-路归并，所以归并排序总的时间复杂度为O（nlog2n）。在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为O(n)。,归并排序的最大特点是，它是一种稳定的排序方法。,返回主目录,类似2-路归并排序，可设计多路归并排序法，归并的思想主要用于外部排序。外部排序可分两步，待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。子文件多路归并，成为较长有序子文件，再记入外存，如此反复，直到整个待排序文件有序。外部排序可使用外存、磁带、磁盘，最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。,返回主目录,9.6 分配类排序,分配类排序则利用分配和收集两种基本操作，基数类排序就是典型的分配类排序。,9.6.1 多关键字排序,例如：我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题。若规定花色和面值的顺序如下：花色：梅花 方块 红桃 黑桃面值：A2310JQK并进一步规定花色的优先级高于面值，则一副扑克牌从小到大的顺序为：梅花A，梅花2，梅花K；方块A，方块2，方块K；红桃A，红桃2，红桃K；黑桃A，黑桃2，黑桃K。,返回主目录,具体进行排序时有两种做法，其中一种是：先按花色分成有序的四类，然后再按面值对每一类从小到大排序。该方法称为“高位优先”排序法。另一种做法是分配与收集交替进行。首先按面值从小到大把牌摆成13叠（每叠4张牌），然后将每叠牌按面值的次序收集到一起，再对这些牌按花色摆成4叠，每叠有13张牌，最后把这4叠牌按花色的次序收集到一起，于是就得到了上述有序序列。该方法称为“低位优先”排序法。,扑克牌的洗牌过程,返回主目录,9.6.2 链式基数排序,基数排序属于上述“低位优先”排序法，通过反复进行分配与收集操作完成排序。,排序时先按最低位的值对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。依此类推，由低位到高位，每一趟都是在前一趟的基础上，根据关键字的某一位对所有记录进行排序，直至最高位，这样就完成了基数排序的全过程。,具体实现时，一般采用链式基数排序。我们首先通过一个具体的例子来说明链式基数排序的基本过程。,返回主目录,(a)初始状态(b)第一趟分配之后(c)第一趟收集之后(d)第二趟分配之后(e)第二趟收集之后(f)第三趟分配之后(g)第三趟收集之后的有序文件,链式基数排序示例,返回主目录,例,算法评价时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n记录数 d关键字数 rd关键字取值范围 空间复杂度：S(n)=2rd个队列指针+n个指针域空间,为了有效地存储和重排记录，算法采用静态链表。有关数据类型的定义如下：,#define RADIX 10#define KEY_SIZE 6#define LIST_SIZE 20typedef int KeyType;typedef struct KeyType keysKEY_SIZE;/*子关键字数组*/OtherType other_data;/*其它数据项*/,返回主目录,int next;/*静态链域*/RecordType1;typedef struct RecordType1 rLIST_SIZE+1;/*r0为头结点*/int length;int keynum;SLinkList;/*静态链表*/typedef int PVectorRADIX;,返回主目录,链式基数排序的有关算法描述如下：,void Distribute(RecordType1 r,int i,PVector head,PVector tail)/*记录数组r中记录已按低位关键字keyi+1，keyd进行过“低位优先”排序。本算法按第i位关键字keyi建立RADIX个队列，同一个队列中记录的keyi相同。headj和tailj分别指向各队列中第一个和最后一个记录（j=0，1，2，RADIX-1）。headj=0表示相应队列为空队列*/for(j=0;j=RADIX-1;+j)headj=0；/*将RADIX个队列初始化为空队列*/p=r0.next；/*p指向链表中的第一个记录*/while(p!=0),返回主目录,j=Order(rp.keyi)；/*用记录中第i位关键字求相应队列号*/if(headj=0)headj=p;/*将p所指向的结点加入第j个队列中*/else rtailj.next=p；tailj=p；p=rp.next；/*Distribute*/,返回主目录,void Collect(RecordType r,PVector head,PVector tail)/*本算法从0到RADIX-1 扫描各队列，将所有非空队列首尾相接，重新链接成一个链表*/j=0；while(headj=0)/*找第一个非空队列*/+j；r0.next=headj；t=tailj；while(jRADIX-1)/*寻找并串接所有非空队列*/+j；while(jRADIX-1)&(headj=0)/*找下一个非空队列*/+j；,返回主目录,if(headj!=0)/*链接非空队列*/rt.next=headj；t=tailj；rt.next=0;/*t指向最后一个非空队列中的最后一个结点*/*Collect*/,返回主目录,void RadixSort(RecordType r,int length)/*length个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序相链接。*/n=length；for(i=0;i=0;-i)/*从最低位子关键字开始，进行d趟分配 和 收集*/Distribute(r，i，head，tail)；/*第i趟分配*/Collect(r，head，tail)/*第i趟收集*/*RadixSort*/,返回主目录,基数排序的算法分析：,对于个记录（每个记录含个子关键字，每个子关键字的取值范围为RADIX个值）进行链式排序的时间复杂度为(RADIX)，其中每一趟分配算法的时间复杂度为()，每一趟收集算法的时间复杂度为(RADIX)，整个排序进行趟分配和收集，所需辅助空间为RADIX个队列指针。当然，由于需要链表作为存储结构，则相对于其它以顺序结构存储记录的排序方法而言，还增加了个指针域空间。,返回主目录,基数排序的顺序表结构,基数排序法也可以利用顺序方式实现。例如：关键字k1k2k3，先按k3扫描一遍，分别记下k3位为0的记录个数，为1的记录个数，为9的记录个数。之后形成两个计数数组num10和cpos10，对上例中按k3位统计的结果下所示：,返回主目录,9.7 各种排序方法的综合比较,首先从算法的平均时间复杂度、最坏时间复杂度、以及算法所需的辅助存储空间三方面，对各种排序方法加以比较。,各种排序方法的性能比较,返回主目录,通过分析和比较，可以得出以下结论：,简单排序一般只用于n值较小的情况；归并排序适用于n值较大的情况；基数排序适用于n值很大而关键字的位数d较小的序列；快速排序是排序方法中最好的方法。从排序的稳定性来看，基数排序是稳定的，除了简单选择排序，其它各种简单排序法也是稳定的。多数情况下，排序是按记录的主关键字进行的，此时不用考虑排序方法的稳定性。如果排序是按记录的次关键字进行的，则应充分考虑排序方法的稳定性。,返回主目录,