数据结构-10内部排序.pps

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第10章 内部排序,10.1 概述,10.2 插入排序,10.3 快速排序,10.4 选择排序,10.5 归并排序,10.6 基数排序,10.7 各种内部排序方法的比较讨论,排序就是将一组杂乱无章的数据按一定的规律顺次排列起来。,排序的目的是为了方便以后的查找。,1,10.1 概述,排序,(Sorting)：简单地说，就是将一组记录按关键字域递增（由小到大）或递减（由大到小）的次序重新排列。,排序码（Sort Key）：作为排序依据的关键字。,有序表：排序后的结果。,无序表：排序前的状态。,升序表正序表：按排序码升序排列的有序表。,降序表逆序表：按排序码降序排列的有序表。,一、概念：,2,稳定排序,：,键值相同的记录，排序后相对次序总能保持不变。,不稳定排序,：,键值相同记录排序前后相对次序不能保持不变。,待排序列： 49,38,65,97,76,13,27,49,排序后:13,27,38,49,49,65,76,97 稳定,排序后:13,27,38,49,49,65,76,97不稳定,内排序,：排序过程全部在内存中进行。,外排序,：排序过程需要进行内存和外存之间的数据交换。,内排序,插入排序（直插排序、二分排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序 （直选排序、树型排序、堆排序）,归并排序（二路归并排序、多路归并排序）,分配排序 （多关键字排序、基数排序）,3,无序区,有序区增长法：,排序表可分成有序区和无序区，随着排序过程的进行，有序区逐渐增长，无序区逐渐缩小，最后全部为有序区，排序结束。初始有序区可为空或仅含一个元素，其余为无序区。,一趟排序,有序区,有序区,无序区,有序度增长法：,排序表不能分成明显的有序区和无序区，但排序过程的每一步，整个排序表的有序程度都提高一点，最后变得完全有序。,4,评价标准：,1）,时间,；,2）,附加空间,。,3）算法的稳定性、复杂程度等,附加空间一般不大，排序经常执行，时间开销是最重标志。,两种基本操作：,1）,比较：,比较关键字的大小,2）,移动：,将记录从一个位置移动到另一个位置。,时间开销主要指关键字的比较次数和记录的移动次数。,当键值是字串时，比较要占用较多的时间；当记录很大时，交换记录时移动要占较多时间。,比较一般都需要，但移动可改变存储方式来避免。,二、时空分析：,5,1）,顺序存储,。对记录本身进行物理重排，移到合适的位置。,2）,链式存储,。无需移动记录，仅修改指针。,（链）表排序,。,3）,索引顺序存储,。对索引表物理重排，不移动原始记录本身。,三、存储方式,const int maxsize=100;/排序表容量，假设为100,typedef int datatype;/假设关键字为int,typedef struct ,datatype key;/关键字域,othertype other;/其它域, rectype;/记录类型,typedef rectype listmaxsize+1;,/排序表类型，0号单元不用（或,作它用，如“监视哨”）,为简单起见，本章以数组作存储结构：,6,10.2 插入排序,基本思想,依次将待排记录插入到有序区适当位置，直到全部记录插入完毕；,初始有序区只有一个元素。,7,一、基本思想,每次将无序区第1条记录插入到有序区适当位置。初始取第1条记录为有序区，其它记录为无序区。随着排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。,有序区也可从排序表的尾部生成,。,10.2.1 直接插入排序,（Straight Insertion Sort）,8,例1：对(49 38 13 76 65 97 27,49,)直接插入排序。,初始：（,49,）,38,13 76,27,49,（,13 38 49,49,65 97,）,（,13 27 38 49 65,）,49,（,13 38 49 76,）,27,49,（,13 38 49,）,76,27,49,（,38,49,）,13,76,27,49,为提高插入时的查找,效率，可以采用,折半查找,称为,折半插入排序,9,void InsertSort(list R,int n) /,无监视哨,int i,j; NODE x; /x为中间结点变量,for(i=2;i=Ri-1.key) continue;,x=Ri; /把待排记录赋给 x,j=i-1;,do /顺序比较和移动,Rj+1=Rj;j-;, while(j0 ,Rj+1=x; /插入Ri,二、算法实现,无序区第一记录Ri 插入有序区R1Ri1，找插入位置和移动记录交替进行：从有序区的后部j开始，如果该位置记录大于待插记录，则后移一位；待插记录插入到最后空出的位置上。,10,void InsertSort(list R,int n) /,有监视哨,int i,j;,for(i=2;i=Ri-1.key) continue;,R0=Ri; /R0是监视哨,j=i-1;,do /顺序比较和移动,Rj+1=Rj;j-;, while(R0.key0”：一旦越界，j=01，循环条件,R0.keyd2,dt,=1,），,所有记录放为同一组，再整体进行一次直接插入排序。,又称“缩小增量排序”（,Diminishing Increment Sort,） 。,10.2.2,希尔排序,14,例如，对（49,38,65,97,76,13,27,49,）希尔排序。,49,27,13,76,97,65,38,49,8,7,6,5,4,3,2,1,49,38,65,97,76,13,27,49,初始关键字,d1=5,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,49,97,76,49,38,65,15,例如，对（49,38,65,97,76,13,27,49,）希尔排序。,8,7,6,5,4,3,2,1,一趟排序结果,d1=3,13,27,49,97,76,49,38,65,13,27,49,97,76,49,38,65,13,27,49,97,76,49,38,65,13,27,49,97,76,49,38,65,13,27,49,97,76,49,38,65,13,27,49,38,76,49,97,65,13,27,49,38,65,49,97,76,16,例如，对（49,38,65,97,76,13,27,49,）希尔排序。,8,7,6,5,4,3,2,1,二趟排序结果,d1=1,13,27,49,38,65,49,97,76,13,27,49,38,65,49,97,76,13,27,49,38,65,49,97,76,13,27,49,38,65,49,97,76,13,27,38,49,65,49,97,76,13,27,38,49,65,49,97,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,17,例如，对（49,38,65,97,76,13,27,49,）希尔排序。,一趟排序结果,13,27,49,97,76,49,38,65,二趟排序结果,13,27,49,38,65,49,97,76,13,27,38,49,49,65,76,97,三趟排序结果,49,27,13,76,97,65,38,49,8,7,6,5,4,3,2,1,初始关键字,18,二、算法实现,void ShellInsert(list R,int n,int h) ,/一趟插入排序，h为本趟增量,int i,j,k;,for(i=1;i=h;i+)/i为组号,for(j=i+h;j=Rjh.key) continue;,R0=Rj;/R0保存待插记录，但不是监视哨,k=jh;/待插记录的前一个记录,do /查找插入位置,Rk+h=Rk;k=kh;/后移记录，继续向前搜索, while(k0 ,Rk+h=R0;/插入Rj,两个,for,循环可合并为一个：,for(j=1+h;j=n;j+),，,相当于对每组交替直接插入排序。,19,void ShellSort(list R,int n,int d,int t) ,/d为增量序列，t为增量序列长度,int i;,for(i=0;it;i+) /各趟插入排序,ShellInsert(R,n,di);,希尔排序就是调用若干趟插入排序：,20,三、效率分析,时间：,O(nlog,2,n),和,O(n,2,),之间，大致,O(n,1.3,),，,优于,直接插入,其一，加速原理。相隔为增量的记录一组，组内移动一位，对原序列则移动若干位，加速向目标位置移动。开始时无序程度大，增量大，加速快；以后每个增量排序后，有序度提高一些，增量缩小，加速减缓。,其二，基本有序和小规模原理。开始时增量大，分组多，组内记录少，组内直接插入快；后来增量缩小，分组少，组内记录多，但有序性提高了，排序也较快。,不稳定：组内“相邻”移动，原序列则跳跃移动,21,10.3,交换排序,基本思想：,每次比较两个待排序的记录，如果关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。,特点：,键值较大的记录向排序表的一端移动，键值较小的记录向另一端移动。,22,一、基本思想,设排序表垂直放置，每个记录看作重量为键值的气泡；根据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。,每一趟一个“最轻”的气泡冒到顶部,上升法,。,也可从上向下扫描，这时每一趟是一个“最重”的气泡沉到底部,下沉法,。,每次交换时，其中一个总沿着最终方向，另一个则未必（取决于上升法还是下降法）。,起泡,排序,（Bubble Sort）,23,例：对（49，38，65，97，76，13，27，49）冒泡排序。,24,void BubbleSort(list R,int n) /上升法冒泡排序,int i,j,flag;,for(i=1;i=i+1;j)/从下向上扫描,if(Rj.keynext=end,end初值为NULL，以后指向每趟最后点。,27,一、基本思想,任选一记录作基准，其它记录与之比较，小于等于放基准前面；大于等于放基准后面。 一趟排序后，左子序列小于等于基准，右子序列大于等于基准。对两子序列进行同样处理，直至,每组只有1个记录，全部记录有序,。,又称,划分交换排序,可看成冒泡排序的改进：记录的比较和交换从两端向中间进行，较大的记录每次交换到较后位置，较小的交换到较前位置，每次移动距离较远，总的比较和移动次数较少。,是目前为止所有内排序中速度最快的一种。,快速排序,（Quick Sorting）,28,1）一趟划分,：,二、算法实现,设划分区间RpRq，指针i、j分别指向p、q。第1记录作基准,j,从右向左扫描，找,1,个小于基准的记录,Rj,，,移到位置,i,；,i,自,i+1,起从左向右扫描，找,1,个大于基准的记录,Ri,，,移到位置,j,再令,j,自,j1,起向左扫描，,如此交替改变扫描方向，从两端往中间靠拢，直至,i=j,时，,i,便是基准的最终位置，将它放在该处。,29,一趟划分,49,27,13,76,97,65,38,49,8,7,6,5,4,3,2,1,初始关键字,49,i,j,49,27,13,76,97,65,38,49,j,i,49,49,13,76,97,65,38,27,j,i,i,49,65,13,76,97,49,38,27,i,j,49,65,49,76,97,13,38,27,i,j,49,65,97,76,49,13,38,27,i,j,j,49,30,49,27,13,76,97,65,38,49,8,7,6,5,4,3,2,1,初始关键字,49,65,97,76,49,13,38,27,49,65,97,76,49,38,27,13,97,76,65,49,49,38,27,13,97,76,65,49,49,38,27,13,97,76,65,49,49,38,27,13,31,例，对（49，38，65，97，76，13，27，49）快速排序,快速排序的,判定树,：,树根表示基准，左右子树表示划分的两个区间，每个子区间继续用子二叉树表示。,32,int Partition(list R,int p,int q) ,/对无序区Rp到Rq划分，返回划分后基准的位置,int i,j;,i=p; j=q; R0=Ri;,/R0作辅助量，存基准(无序区第一个记录),while(i=R0.key ,/从右向左扫描,if(ij) Ri=Rj;i+;/交换Ri和Rj,while(Ri.key=R0.key ,/从左向右扫描,if(i=t) return;/只有一个记录或无记录无需排序,i=Partition(R,s,t);/对Rs到Rt做划分,QuickSort(R,s,i1);/递归处理左区间,QuickSort(R,i+1,t);/递归处理右区间,2）快速排序算法,设排序区间为Rs到Rt，一趟划分后得到基准位置i，接着对区间Rs到Ri1、Ri+1到Rt进行递归处理。,对整个排序表,R,进行快速排序，调用,QuickSort(R,1,n),；,34,时间：,最好：每次划分两侧大致相等，判定树高,log,2,n,1,，,C,min, n(log,2,n+1)=O(nlog,2,n),最坏：每次划分一侧空，剩下另一侧，判定树为单枝树，蜕化为冒泡排序 ：,移动次数不大于比较的次数,平均：,O(n log,2,n),辅助空间为栈，深度最好,O (log,2,n),，,最坏,O(n),。,不稳定：两头比较和交换，可改变相同键值记录的相对位置,三、效率分析,35,10.4 选择排序,（Selection Sort）,基本思想每一趟从待排记录中选关键字最小（或最大）的记录，顺序放在已排序的子序列的最后（或最前），直到全部记录排完,36,一、基本思想,所有记录组成初始无序区，每趟都从无序区中选出键值最小的记录，与无序区第一个记录交换，有序区增加了一个记录。n1趟排序后，整个排序表就全部有序了。,可看成冒泡排序：比较和交换的是无序区最小和无序区第一个，不是相邻两个。总比较次数相同，但移动次数少。,10.4.1 简单选择排序,（Straight Selection Sort）,37,例，对（49，38，65，97，76，13，27，49）简单选择排序,38,void SelectSort(list R,int n) ,int i,j,k;,for(i=1;i=n1;i+) /n1趟排序,k=i;,for(j=i+1;j=n;j+)/无序区中找最小Rk,if(Rj.key,n/2,的结点都是叶子，以这些结点为根的子树均已是堆。,依次将以序号为,n/2,，,n/2,1,1的结点作为根的子树都调整为堆。,按该次序调整各结点时，其左、右子树均已是堆（不妨将空树亦看作是堆）。,已知结点Ri的左、右子树是堆，如何将以Ri为根的完全二叉树调整为堆？,解决这一问题可采用“,筛选法,”。,48,筛选法：,Ri左、右子树是堆，其根为各自子树中关键字最大者，,将Ri和其左、右孩子中关键字最大者放到Ri的位置。,若Ri是三者中的最大，则无需调整，以其为根的子树已是堆；,否则，将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。,交换后以R2i和R2i+1为根的子树可能不再是堆，但其左、右子树仍然是堆，于是重复上述过程，将子树调整为堆，如此逐层递推下去，最多可能一直调整到树叶。,这一过程就像过筛子一样，把较小的关键字筛下去，而将最大关键字一层层地选择上来。,49,1,9,8,10,6,2,16,11,5,4,大根堆,16,9,8,10,6,2,1,11,5,4,16,9,8,10,6,2,11,1,5,4,16,9,8,1,6,2,11,10,5,4,例，,筛选法（大根堆）示例,。,50,1,9,8,10,6,16,2,11,4,5,例，对（1,2,9,11,4,6,8,10,16,05）建初始堆（大根）。,n=10，故从第,10,/2,5个结点开始进行调整,1,9,8,10,6,16,2,11,5,4,1,9,8,10,6,11,2,16,5,4,1,9,8,10,6,11,2,16,5,4,51,1,9,8,10,6,11,16,2,5,4,1,9,8,10,6,2,16,11,5,4,16,9,8,10,6,2,1,11,5,4,16,9,8,10,6,2,11,1,5,4,16,9,8,1,6,2,11,10,5,4,52,2、调整和重建,将堆顶元素与堆最后的元素互换；,将其余的元素筛选成堆；,53,16,9,8,1,6,2,11,10,5,4,交换,筛选,交换,筛选,4,9,8,1,6,2,11,10,5,16,11,9,8,1,6,2,10,4,5,16,2,9,8,1,6,11,10,4,5,16,54,交换,筛选,交换,筛选,10,9,8,1,6,11,5,4,2,16,1,9,8,10,6,11,5,4,2,16,9,8,1,10,6,11,5,4,2,16,1,8,9,10,6,11,5,4,2,16,55,交换,筛选,交换,筛选,8,6,9,10,1,11,5,4,2,16,1,6,9,10,8,11,5,4,2,16,6,1,9,10,8,11,5,4,2,16,2,1,9,10,8,11,5,4,6,16,56,交换,筛选,交换,筛选,5,1,9,10,8,11,4,2,6,16,2,1,9,10,8,11,4,5,6,16,4,1,9,10,8,11,2,5,6,16,1,4,9,10,8,11,2,5,6,16,57,交换,2,4,9,10,8,11,1,5,6,16,1,4,9,10,8,11,2,5,6,16,58,void HeapSort(list R,int n) ,/对R1到Rn进行堆排序,int i;,for(i=n/2;i=1;i) Sift(R,i,n);/建初始堆,for(i=n;i=2;i) /进行n1趟堆排序,R0=R1;R1=Ri;Ri=R0;,/堆顶和当前堆底交换，R0作辅助量,Sift(R,1,i1);/R1到Ri1重建成新堆,三、算法实现,59,void Sift(list R,int p,int q) ,/筛选，范围RpRq，非递归,int i,j;,R0=Rp;/R0辅助量，保存原根结点,i=p;/i指向待调整点,j=2*i;/j指向Ri的左孩子,while(j=q) /,无左孩子，必叶子，结束,if(jRj.key) break;,/根孩子，已堆，调整结束,Ri=Rj;/将Rj换到双亲位置上,i=j;/修改当前被调整结点,j=2*i;/j指向Ri的左孩子,Ri=R0;/原根结点放入正确位置,60,void Sift2(list R,int p,int q) ,/筛选，范围RpRq，递归,int i,j;,if(p=q) return;/只有一个元素或无元素,i=p;/i指向待调整点,j=2*i; /j指向Ri的左孩子,if(jRj.key) return;,/待调点已最大，不调,R0=Rj;Rj=Ri;Ri=R0;,/交换Rj和Ri，R0作辅助,Sift2(R,j,q);/递归,61,建堆,n/2,筛选，重建,n1,次筛选，每次筛选双亲和孩子比较和移动，不超过深度，时间复杂度,(,n/2,n1)O(log,2,n) =O(nlog,2,n),。,辅助空间为,1,（供交换用），空间复杂度为,O(1),。,不稳定，如（,2,，,1,，,2,）,四、效率分析,62,一、 二路归并排序基本思想,初始排序表看成n个长度为1的有序子表，两两归并，得到,n/2,个有序的子表（当n为奇数时，归并后仍有一个长度为1的子表）；再把这些有序子表两两归并，如此反复，直到最后得到一个长度为n的有序表为止。,10.5 归并排序,（Merging Sort）,利用“归并”技术来进行排序，所谓归并是指将若干个已排序的子表合并成一个有序表。,63,例，（49，38，65，97，76，13，49）二路归并排序。,64,void Merge(list R,list R1,int low,int mid,int high) ,/合并RlowRmid、Rmid+1Rhigh，结果在R1中,int i,j,k;,i=low;j=mid+1;k=low;,while(i=mid & j=high),if(Ri.key=Rj.key) R1k+=Ri+;/小者,else R1k+=Rj+;,while(i=mid) R1k+=Ri+;/复制左子表剩余,while(j=high) R1k+=Rj+;/复制右子表剩余,1、两子表合并,二、算法实现,65,void MergePass(list R,list R1,int n,int len) ,/对R做一趟归并，结果在R1中,int i,j;,i=1;/i指向第一对子表的起始点,while(i+2*len1=n) /归并长度为len的两个子表,Merge(R,R1,i,i+len1,i+2*len1);,i=i+2*len;/i指向下一对子表起始点,if(i+len1n)/剩两子表，一个长度小于len,Merge(R,R1,i,i+len1,n);,else/子表个数为奇数,剩一段,for(j=i;j=n;j+)/将最后一个子表复制到R1中,R1j=Rj;,2、一趟归并,设子表长度len，对子表个数奇数、最后子表长度小于len两种情况特殊处理。,66,void MergeSort(list R,list R1,int n) ,/对R二路归并排序，结果在R中(非递归),int len;,len=1;,while(lenn) ,MergePass(R,R1,n,len);len=len*2;,/一趟归并，结果在R1中,MergePass(R1,R,n,len);len=len*2;,/再次归并，结果在R中,3、归并排序,若干次调用“一趟归并”，每趟子表长度扩大一倍。第一趟子表长度为1，当子表长度n时结束。,67,三效率分析,子表长度不断加倍，,1n,，,归并趟数为,log,2,n,；,每趟归并比较次数,移动次数，后者为,O(n),；,总时间复杂度,O(nlog,2,n),。,辅助空间为数组,R1,，,空间复杂度,O(n),键值相同记录顺序复制，不改变相对位置，故是稳定的。,可在链表上实现,68,10.6 基数排序,利用关键字结构，通过“,分配,”和“,收集,”实现排序,无需比较关键字。,可分为箱排序和基数排序两类。,69,箱排序、桶排序,Bin Sort、Bucket Sort,设置若干箱子，扫描待排记录R1、R2、Rn，把关键字等于k的记录全都装入到第k个箱子（分配），然后，按序号依次将各非空的箱子首尾连接起来（收集）。,例，扑克牌按面值A2JQK排序（不分花色），设置13个“箱子”，依次将每张牌按面值放入相应的箱子里，然后依次将箱子首尾相接，就得到按面值递增序排列的一副牌。,箱子个数,m,取决于关键字的取值范围。,分配时间,(n),，,收集时间,(m+n),（,若用链表，则,(m),），,所以箱排序时间,(m+n),。,若关键字的取值范围很大，如,m=(n,2,),，,则效率很低。,70,基数排序,（Radix Sort）,多关键字排序：低位优先，,高位优先,每趟箱子共用，每趟排序前清空箱子（除第一趟外）,箱子的数据按队列存放,箱子内数据个数可变，适合链表实现,链式基数排序,将关键字看成多个分量组成，从低到高依次对关键字的各分量进行箱排序，每趟所需箱子数就是基数。,时间：链表初始化,O(n),，,清箱,O(r),，,收集,O(r),，,分箱,O(n),，,一趟总,O(n+r),，,d,趟总,O(d(n+r)O(n),。,空间：结点指针,O(n),，,箱子头尾指针,O(r),，总,O(n+r),稳定：分配和收集不改变相同键值的相对位置。,71,例对（,91 46 85 15 92 35 31 22）基数排序,0,1,2,3,4,5,6,7,8,9,91,46,85,15,92,35,31,22,收集,: 91 31 92 22 85 15 35 46,0,1,2,3,4,5,6,7,8,9,91,31,92,22,85,15,35,46,收集,:,15 22 31 35 46 85 91 92,分配(按个位),分配(按十位),72,10.7,内排序的比较和选择,简单排序,（直接插入、直接选择、冒泡排序等）每次只对相邻元素比较，前进步伐慢，时间耗费大，为(n,2,)，但一些特殊情况却可取得很好效果；效率高的算法每次比较产生的作用不仅仅局限于被比较的两个元素，而是多个甚至一半左右，但它们对数据量小的情况并不一定合适。,综合考虑下列因素：,（1）待排序的记录数目。,（2）记录本身信息量的大小。,（3）关键字的结构及其分布情况。,（4）对排序稳定性的要求。,（5）语言工具的条件。,（6）算法本身的难易程度。,（7）辅助空间的大小等。,73,