排序北京师范大学课件.ppt

1、第第8章章 排序排序一、基本概念一、基本概念 排序排序：指将一组数据元素按照一个或多个关键字排列成有序：指将一组数据元素按照一个或多个关键字排列成有序序列的过程。序列的过程。排序的排序的稳定性稳定性：如果任意两个关键字相同的数据元素：如果任意两个关键字相同的数据元素Ei和和Ej，在排序前后相对位置不变在排序前后相对位置不变(比如比如Ei在排序之前和之后都位于在排序之前和之后都位于Ej的前面的前面)，那么称这种排序是稳定的，否则称这种排序是，那么称这种排序是稳定的，否则称这种排序是不稳定的。不稳定的。内排序内排序：待排序的序列在排序过程中全部都存放在内存中。：待排序的序列在排序过程中全部都存放在

2、内存中。外排序外排序：待排序序列在排序过程中需要访问外存储器：待排序序列在排序过程中需要访问外存储器(比如比如文件文件)。二、内排序二、内排序插入排序插入排序(1)直接插入排序直接插入排序void insort(elemtype r,int n)/*对表长是n的顺序表r进行升序排序*/int i,j;elemtype tmp;for(i=1;i=0&rjtmp)/*自右向左扫描有序子序列，如果数据元素比tmp大，就向右移动一个单元*/rj+1=rj;j-;rj+1=tmp;/*tmp的正确为止是j+1*/最好时间复杂度最好时间复杂度 最坏时间复杂度最坏时间复杂度)(nO)(2nO二、内排序二、

3、内排序插入排序插入排序(2)二路插入排序二路插入排序void binsort(elemtype r,int n)int first,last;int i,j,k;elemtype*a;a=(elemtype*)malloc(n*sizeof(elemtype);/*分配存放有序子序列的数组a*/if(a=NULL)return;a0=r0;/*以r0为界，将r0复制到a0*/first=last=0;/*初始化首单元和尾单元指针*/二、内排序二、内排序插入排序插入排序(3)for(k=1;k=a0)/*将rk插入到a0的右边*/i=last;while(i=0&airk)ai+1=ai;i-;

4、ai+1=rk;last+;else/*将rk插入到a0的左边，即从数组末尾向左插*/first-;if(first=-1)first=n-1;i=first+1;while(in&ai=rk)/*为了使排序是稳定的，此处使用为了使排序是稳定的，此处使用=*/ai-1=ai;i+;ai-1=rk;/*属于for语句*/二、内排序二、内排序插入排序插入排序(4)i=first;/*将有序序列从a复制到r中*/k=0;while(kn)rk=ai;k+;i=(i+1)%n;free(a);最好时间复杂度最好时间复杂度 最坏时间复杂度最坏时间复杂度)(2nO)(nO二、内排序二、内排序插入排序插入排

5、序(5)希尔排序希尔排序0123491141517r56789153 1149111415175311401234153 r56789911415171141101234153 r5678991141517114151117439154012341 3 4r5678991151517411012341 3 4r567899115151714113411159517411012341 354r56789911 15174110123413 45r56789911 1517114(1)一趟排序的结果一趟排序的结果(2)二趟排序的结果二趟排序的结果(3)三趟排序的结果三趟排序的结果(4)最后一趟排序

6、的结果最后一趟排序的结果二、内排序二、内排序插入排序插入排序(6)void ShellInsert(elemtype r,int n,int dlta)/*对表长为n的顺序表r进行一趟希尔排序*/int i,j,k;elemtype tmp;/*以dlta为间隔取数据元素为子序列，对子序列进行直接插入排序，子序列的数量必定是dlta*/for(i=0;idlta;i+)for(j=dlta+i;j=0&rktmp)rk+dlta=rk;k-=dlta;rk+dlta=tmp;二、内排序二、内排序插入排序插入排序(7)void ShellSort(elemtype r,int n)int dlt

7、a;dlta=(n+1)/2;/*间隔的初始值*/while(dlta1)ShellInsert(r,n,dlta);dlta=(dlta+1)/2;/*间隔值折半*/ShellInsert(r,n,1);/*最后一趟希尔排序*/二、内排序二、内排序交换排序交换排序(1)起泡排序起泡排序void BubbleSort(elemtype r,int n)/*对表长是n的顺序表r进行起泡排序*/int i,j;elemtype tmp;for(i=1;in;i+)/*一共需要n-1趟起泡*/for(j=0;jrj+1)/*发现逆序关系，交换数据元素*/tmp=rj;rj=rj+1;rj+1=tmp

8、;时间复杂度：时间复杂度：)(2nO二、内排序二、内排序交换排序交换排序(2)起泡排序的改进起泡排序的改进如果在一趟起泡过程中，没有发生交换操作，就不再需要起泡操作；如果在一趟起泡过程中，没有发生交换操作，就不再需要起泡操作；记下最后一次交换操作的位置记下最后一次交换操作的位置t，下次起泡区间是，下次起泡区间是r0.t而不是而不是r0.n-i。用用“传送传送”代替交换。代替交换。在两个方向上都起泡。在两个方向上都起泡。void BubbleSort1(elemtype rN,int n)/*改进的起泡排序*/int low,high,i,j;int t;elemtype tmp;high=n-

9、1;low=0;t=0;/*从左向右方向上，起泡区间初始起点是0，终点是n-1*/二、内排序二、内排序交换排序交换排序(3)while(highlow)/*开始从左向右起泡*/low=t;/*起泡区间被标识为rlow.high*/i=low;t=0;/*假定未发生交换*/while(iri+1)/*发现逆序，执行传送操作*/tmp=ri;/*保存ri*/while(iri+1)/*将比tmp小的数据元素向左移动*/ri=ri+1;i+;ri=tmp;/*将tmp放到正确的位置上*/t=i-1;/*如果这是最后一次传送，那么t就是新起泡区间的终点*/i+;if(t=0)break;/*未发生交换

10、，r已经有序，跳出*/二、内排序二、内排序交换排序交换排序(4)/*开始自右向左起泡*/high=t;/*设定起泡区间的新终点*/i=high;t=0;while(ilow)if(rilow&tmpri-1)ri=ri-1;i-;ri=tmp;t=i+1;/*如果这是最后一次传送，那么t就是新起泡区间的起点*/i-;if(t=0)break;/*未发生交换操作，r已经有序，跳出*/二、内排序二、内排序交换排序交换排序(5)快速排序快速排序【基本思想基本思想】以某个数据元素以某个数据元素PK（通常是（通常是r0）为分界，将序列划分为两个）为分界，将序列划分为两个子序列，左边的子序列的数据元素都不

11、大于子序列，左边的子序列的数据元素都不大于PK，右边的子序列的数据元素，右边的子序列的数据元素都不小于都不小于PK。然后对左右子序列进行同样的分割操作，直到子序列长度是。然后对左右子序列进行同样的分割操作，直到子序列长度是1为止。为止。012349114521r56789171513 114pivotkey9lowhigh012349114521r56789171513 114lowhigh4012349114521r56789171513 11114lowhigh01234954921r56789171513 11114lowhigh(1)初始化的结果初始化的结果(2)一次下行的结果一次下行

12、的结果(3)一次上行的结果一次上行的结果01234954521r56789171513 11114lowhighhigh(4)一次下行的结果一次下行的结果(5)一次上行的结果一次上行的结果，分割完毕分割完毕二、内排序二、内排序交换排序交换排序(6)void Part(elemtype r,int l,int h,int*pivotloc)/*将序列r的区间rl.h分割成两个子序列，最终的分界点由pivotloc返回*/int low,high;elemtype pivotkey;/*PK值*/low=l;high=h;/*初始化high，low*/pivotkey=rlow;/*保存PK值，P

13、K的初始位置是low*/while(high!=low)/*未分割完，继续分割循环*/while(low=pivotkey)high-;/*high的下行*/if(lowhigh)rlow=rhigh;/*将rhigh放到PK的左边，PK的位置变为high*/low+;/*准备low上行*/while(lowhigh&rlow=pivotkey)low+;/*low上行*/if(lowl)/*如果序列长度大于1*/Part(r,l,h,&i);/*分割序列，分界点是i*/*递归调用快速排序算法，对两个子序列分别进行快速排序*/QuickSort(r,l,i-1);QuickSort(r,i+1

14、,h);最好时间复杂度：最好时间复杂度：最坏时间复杂度：最坏时间复杂度：)(2nO)log(2nnO二、内排序二、内排序选择排序选择排序(1)简单选择排序简单选择排序void SelectSort(elemtype r,int n)/*对表长是n的序列r进行直接选择排序*/int i,j,k;elemtype tmp;for(i=1;in;i+)/*进行n-1次选择*/k=0;/*先假定最大值是r0*/for(j=k+1;jrk)k=j;/*记录新的最大值的位置*/if(k!=n-i)/*如果最大值不是最后一个单元，则与最后一个单元交换*/tmp=rn-i;rn-i=rk;rk=tmp;二、内

15、排序二、内排序选择排序选择排序(2)树形选择排序树形选择排序树形选择排序树形选择排序,又称锦标赛排序。它的基本思想就是将序列中的相邻元素两又称锦标赛排序。它的基本思想就是将序列中的相邻元素两两比较，选出较大值，然后将这些两两比较的结果再两两比较，这种重复操两比较，选出较大值，然后将这些两两比较的结果再两两比较，这种重复操作直至选出序列的最大值为止。作直至选出序列的最大值为止。(a)序列序列1,5,7,3,2的比赛树的比赛树(b)删除最大值的结果删除最大值的结果(c)经过调整后经过调整后5成为根成为根32315737732315*3*32315*355二、内排序二、内排序选择排序选择排序(3)堆

16、排序堆排序一个顺序存储的完全二叉树，如果任何一个结点的值都不小于或不大一个顺序存储的完全二叉树，如果任何一个结点的值都不小于或不大于它左右子树（如果有的话）中所有结点的值，那么这个顺序存储的于它左右子树（如果有的话）中所有结点的值，那么这个顺序存储的序列就是堆。这个二叉树的根被称为堆顶，最后一层最右端的叶子结序列就是堆。这个二叉树的根被称为堆顶，最后一层最右端的叶子结点称为堆底。点称为堆底。由于堆是一个顺序存储的完全二叉树，所以一个长度是由于堆是一个顺序存储的完全二叉树，所以一个长度是n的序列要成的序列要成为一个堆，必须存储在容量是为一个堆，必须存储在容量是n+1的顺序表中，其中的顺序表中，其

17、中0号单元不用。号单元不用。堆顶堆顶r1是整个序列的最大值或者最小值。堆顶是最大值的堆被称为是整个序列的最大值或者最小值。堆顶是最大值的堆被称为大顶堆或者极大堆；堆顶是最小值的堆被称为小顶堆或者极小堆。大顶堆或者极大堆；堆顶是最小值的堆被称为小顶堆或者极小堆。73291311151716197329131115121619171321199111625472(a)(b)(c)二、内排序二、内排序选择排序选择排序(4)【堆排序的基本思想堆排序的基本思想】首先将一个序列构建成堆；然后将堆顶与堆底交换，再去首先将一个序列构建成堆；然后将堆顶与堆底交换，再去掉堆底，剩余的序列可能不是堆，将它再调整成堆

18、，再将掉堆底，剩余的序列可能不是堆，将它再调整成堆，再将堆顶与堆底交换。如此重复直到堆只有一个结点为止。堆顶与堆底交换。如此重复直到堆只有一个结点为止。【需要解决的需要解决的2个问题个问题】如何将一个替换掉堆顶的堆重新调整成堆？如何将一个替换掉堆顶的堆重新调整成堆？一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如何将这棵二叉树调整成堆。何将这棵二叉树调整成堆。如何将一个序列建成一个堆？如何将一个序列建成一个堆？二、内排序二、内排序选择排序选择排序(5)如何将一个替换掉堆顶的堆重新调整成堆？如何将一个替换掉堆顶的堆重新调整成

19、堆？一个完全二叉树，根的左右子树都是堆，而整棵二叉树不一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如何将这棵二叉树调整成堆。是堆。问如何将这棵二叉树调整成堆。73261311151716197321311151716673213111517161767321311151316176(1)一个大顶堆一个大顶堆(2)堆顶堆底交换的结果堆顶堆底交换的结果(3)6第一次下沉第一次下沉(4)6第二次下沉第二次下沉(5)6第三次下沉第三次下沉，调整结束调整结束732711151316176二、内排序二、内排序选择排序选择排序(6)如何将一个序列建成一个堆？如何将一个序列建成一个堆？21 43

20、5二、内排序二、内排序选择排序选择排序(7)void Adjust(elemtype r,int k,int n)/*将表长是n的序列r看成是完全二叉树的顺序存储，将以rk为根的子树调整成大顶堆*/int i,j;elemtype tmp;tmp=rk;/*用tmp保存rk*/i=k;while(2*i=n)/*逐层上浮的相应结点，确定rk下沉的终点位置*/*ri不是叶子结点，继续循环*/j=2*i;/*rj是rk的左孩子，准备上浮左孩子结点*/if(j+1rj)j+;/*右孩子比左孩子大，上浮右孩子结点*/if(tmp=1;i-)Adjust(r,i,n);for(i=n;i=2;i-)/*

21、进行n-1次选择，即摘取堆顶，与堆底交换。选择后将剩余部分调整成堆*/tmp=ri;/*ri是堆底,r1是堆顶，堆底和堆顶交换*/ri=r1;r1=tmp;Adjust(r,1,i-1);/*将序列r1.i-1调整成堆*/时间复杂度：时间复杂度：)log(2nnO二、内排序二、内排序索引排序索引排序(1)索引排序索引排序void indexsort(elemtype r,int n,int index)/*index是r的索引表，对索引表进行排序，表长是n*/int i,j,tmp;for(i=1;i=0&rindexjrtmp)indexj+1=indexj;j-;indexj+1=tmp;

22、012345670123456701234567mathphysicschemstryhistorybiologyartgeographymusic012345675426307101234567mathphysicschemstryhistorybiologyartgeographymusic(a)字符串数组的索引表字符串数组的索引表(b)排序的字符串数组索引表排序的字符串数组索引表rindexrindex二、内排序二、内排序索引排序索引排序(2)索引排序后的物理重排索引排序后的物理重排void arrange(elemtype r,int n,int index)/*index是r的有序索

23、引表，r的表长是n，对r按照索引进行物理重排*/int i,j,k;elemtype tmp;for(i=0;in;i+)if(indexi!=i)/*ri需要调整*/tmp=ri;/*用用tmp保存保存ri*/j=i;k=indexj;/*自此，rk应该放到rj的位置上，除非k等于i*/二、内排序二、内排序索引排序索引排序(3)while(k!=i)rj=rk;/*rj空闲，将rk复制到rj中*/indexj=j;/*调整索引表指针值*/j=k;/*这时rj又空闲*/k=indexj;/*while循环退出，说明k等于i，而ri已经是调整好的数据，需要放到rj中去的数据是原来的ri,它保存在

24、tmp中*/rj=tmp;indexj=j;二、内排序二、内排序计数排序计数排序(1)计数排序计数排序【基本思想基本思想】设定一个计数器数组，记录每个数据元素比它小的数据元素的设定一个计数器数组，记录每个数据元素比它小的数据元素的个数。个数。计数排序需要物理重排计数排序需要物理重排0126453752942317116rcount0126453720417653(2)将将 tm p 1 复复 制制 到到 r 2 中中0126453752542 31 71 16rc o u n t0126453720417653ijk59tm p 1tm p 2(1)c o u n t0 不不 是是 0，需需

25、要要 调调 整整 r 0 0126453752942 31 71 16rc o u n t0126453720417653i5 tm p 1tm p 2(3)将将 tm p 1 复复 制制 到到 r 4 中中01264537525491 71 16rc o u n t0126453720217653ijk92 3tm p 1tm p 2(5)将将 tm p 1 复复 制制 到到 r 3 中中01264537525491 71 12 3rc o u n t0126453720214653ijk2 36tm p 1tm p 2(4)将将 tm p 1 复复 制制 到到 r 7 中中01264537

26、525491 762 3rc o u n t0126453720214657ijk61 1tm p 1tm p 2(6)将将 tm p 1 复复 制制 到到 r 5 中中01264537525491 162 3rc o u n t0126453720214637ijk1 11 7tm p 1tm p 2(7)将将 tm p 1 复复 制制 到到 r 6 中中012645375251 791 162 3rc o u n t0126453720214537ijk1 74tm p 1tm p 2(8)将将 tm p 1 复复 制制 到到 r 1 中中012645375451 791 162 3rc

27、o u n t0126453720264537ijk42tm p 1tm p 2(9)将将 tm p 1 复复 制制 到到 r 0 中中012645372451 791 162 3rc o u n t0126453721264537ijk25tm p 1tm p 2012645372451 791 162 3rc o u n t0126453701264537ij tm p 1tm p 2(1 0)调调 整整 完完 毕毕二、内排序二、内排序计数排序计数排序(2)void CountSort(elemtype r,int n)int*count;int i,j,k;elemtype tmp1,t

28、mp2;count=(int*)malloc(n*sizeof(int);if(count=NULL)return;for(i=0;in;i+)counti=0;/*将计数器都清零*/for(i=0;in-1;i+)for(j=i+1;j=rj)counti+;/*如果ri大，则counti增1，否则countj增1*/else countj+;二、内排序二、内排序计数排序计数排序(3)/*下面开始对r进行物理重排*/for(i=0;in;i+)if(counti!=i)/*开始调整ri*/j=i;/*j指向要调整的单元*/k=countj;/*k指向要覆盖的单元*/tmp1=rj;/*用tm

29、p1保存要移动的数据单元*/while(k!=i)/*调整循环*/tmp2=rk;/*用tmp2保存要被覆盖的数据单元*/rk=tmp1;/*将tmp1复制到rk中*/j=k;/*j指向k，rj已经保存在tmp2中了*/k=countj;/*k指向下一个要覆盖的单元*/countj=j;/*调整计数器信息*/tmp1=tmp2;/*将rj保存到tmp1中，准备移动到rk，tmp2要保存那个rk*/ri=tmp1;/*tmp1所保存的数据应该位于ri*/counti=i;free(count);二、内排序二、内排序归并排序归并排序(1)归并排序归并排序void MergeSort(elemtyp

30、e r,int n)/*对长度是n的序列r进行归并排序*/int low,high,len;len=1;/*有序子表长度一开始是1*/while(lenn)/*只要子表长度小于n，就需要一趟合并操作*/low=0;/*合并区间的起点一开始是0*/while(low+len=n)high=n-1;/*说明第2个子序列要短一些*/*调用函数SegmentMerge，将区间rlow.high内的2个子序列合并*/if(!SegmentMerge(r,low,high,len)return;low=high+1;/*确定下一个合并区间的起点*/len*=2;/*有序子序列的长度增倍*/二、内排序二、内

31、排序归并排序归并排序(2)int SegmentMerge(elemtype r,int low,int high,int len)/*rlow.high区间内存在着两个长度是n的有序子序列，将它们合并成1个有序子序列*/elemtype*r1,*r2;/*r1,r2是两个辅助空间，分别存放两个有序子序列*/int size1,size2;/*分别是r1,r2空间的大小*/int i,j,k;size1=len;size2=high-low+1-len;/*确定r1,r2的大小*/r1=(elemtype*)malloc(size1*sizeof(elemtype);r2=(elemtype*

32、)malloc(size2*sizeof(elemtype);if(r1=NULL|r2=NULL)return 0;/*将区间rlow.high中的2个子序列分别复制到r1,r2中*/for(i=0;isize1;i+)r1i=rlow+i;for(i=0;isize2;i+)r2i=rlow+size1+i;二、内排序二、内排序归并排序归并排序(3)/*下面开始将r1,r2有序合并到rlow.high中*/i=0;j=0;k=low;while(isize1&jsize2)if(r1i=r2j)rk+=r1i+;else rk+=r2j+;while(isize1)rk+=r1i+;whi

33、le(jsize2)rk+=r2j+;/*释放辅助空间，返回*/free(r1);free(r2);return 1;时间复杂度：时间复杂度：)log(2nnO二、内排序二、内排序基数排序基数排序(1)基数排序是一种利用多关键字排序的思想对单关键字序列进行基数排序是一种利用多关键字排序的思想对单关键字序列进行排序的方法。排序的方法。对多关键字数据元素进行排序有两种方式：对多关键字数据元素进行排序有两种方式：最高位优先法（最高位优先法（MSD）：先排最高位关键字）：先排最高位关键字最低位优先法（最低位优先法（LSD）：先排最低位关键字。）：先排最低位关键字。基数排序的基本思想是：将单个关键字看成

34、是多个关键字的组基数排序的基本思想是：将单个关键字看成是多个关键字的组合，利用多关键字的合，利用多关键字的LSD方法，对序列进行方法，对序列进行d（d是多关键字的是多关键字的个数）趟排序，最终成为有序序列。个数）趟排序，最终成为有序序列。链式基数排序：将序列组织成静态链表的基数排序链式基数排序：将序列组织成静态链表的基数排序链式基数排序的基本操作：链式基数排序的基本操作：分配分配收集收集01234567891 0 6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 61236767891 00k e yn e x t01234567891 0 6

35、1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 684067211 0935h e a d8ta il90123456789h e a d3ta il6h e a d0ta il0h e a d0ta il0h e a d1ta il1h e a d4ta il7h e a d1 0ta il1 0h e a d5ta il5h e a d2 ta il2h e a d0ta il06 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 6分分 配配 前前 的的 序序 列列分分 配配 的的 结结 果果收收

36、集集 的的 结结 果果5 3 07 9 09 2 11 0 16 1 44 8 52 1 53 0 66 3 77 3 8收收 集集 后后 的的 序序 列列(2)第第 1 次次 分分 配配 和和 收收 集集6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 6(1)初初 始始 化化 的的 状状 态态01234567891 0 6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 61234567891 00k e yn e x th e a d0ta il00123456789h e a d0ta il0

37、h e a d0ta il0h e a d0ta il0h e a d0ta il0h e a d0ta il0h e a d0ta il0h e a d0ta il0h e a d0ta il0h e a d0ta il06 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 6分分 配配 前前 的的 序序 列列k e yn e x t01234567891 0 6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 66748921 03501h e a d6t a il1 00123456789h e a

38、 d1t a il7h e a d3t a il3h e a d8t a il2h e a d0t a il0h e a d0t a il0h e a d0t a il0h e a d0t a il0h e a d4 t a il4h e a d9t a il9分分 配配 前前 的的 序序 列列分分 配配 的的 结结 果果收收 集集 的的 结结 果果1 0 13 0 66 1 42 1 59 2 15 3 06 3 77 3 84 8 57 9 0收收 集集 后后 的的 序序 列列(3)第第 2 次次 分分 配配 和和 收收 集集5 3 07 9 09 2 11 0 16 1 44 8 52

39、1 53 0 66 3 77 3 801234567891 0 6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 68706721 01 05355 3 07 9 09 2 11 0 16 1 44 8 52 1 53 0 66 3 77 3 8k e yn e x t01234567891 0 6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 665908271 0134h e a d0t a il00123456789h e a d6t a il6h e a d7t a il7h e a d1

40、0t a il1 0h e a d4t a il4h e a d8t a il8h e a d1t a il5h e a d2t a il9h e a d0 t a il0h e a d3t a il3分分 配配 前前 的的 序序 列列分分 配配 的的 结结 果果收收 集集 的的 结结 果果1 0 12 1 53 0 64 8 55 3 06 1 46 3 77 3 87 9 09 2 1收收 集集 后后 的的 序序 列列(4)第第 3 次次 分分 配配 和和 收收 集集5 3 07 9 09 2 11 0 16 1 44 8 52 1 53 0 66 3 77 3 81 0 13 0 66

41、1 42 1 59 2 15 3 06 3 77 3 84 8 57 9 001234567891 0 6 1 47 3 89 2 14 8 56 3 71 0 12 1 55 3 07 9 03 0 66598921 03501二、内排序二、内排序基数排序基数排序(2)链式基数排序链式基数排序typedef struct int key;int next;REC;void RadixSort(int r,int d,int radix,int n)REC*rec;int*head,*tail;char str6,formatstr10;int i,j,k;rec=(REC*)malloc(n

42、+1)*sizeof(REC);/*0号单元是头结点，需要n+1单元*/head=(int*)malloc(radix*sizeof(int);tail=(int*)malloc(radix*sizeof(int);if(rec=NULL|head=NULL|tail=NULL)return;rec0.next=1;for(i=0;i=0;i-)for(j=0;jradix;j+)/*将所有的队列初始化为空队列*/headj=0;tailj=0;/*遍历整个静态链表，开始一趟分配*/k=rec0.next;/*k指向第1个整数*/while(k!=0)sprintf(formatstr,%0%

43、dd,d);sprintf(str,formatstr,reck.key);j=stri-0;if(tailj=0)/*队列空时，队首队尾指针都是k*/headj=tailj=k;else/*如果队不空，则将队尾元素的后继指向当前整数，并修改队尾指针*/rectailj.next=k;tailj=k;k=reck.next;/*k指向静态链表中下一个整数*/二、内排序二、内排序基数排序基数排序(4)/*开始一趟收集*/j=0;while(headj=0)j+;/*寻找第一个非空队列*/rec0.next=headj;/*收集后的静态链表第1个整数就是该非空队列的首单元*/k=j+1;while

44、(kradix)/*将剩余的队列按照顺序首尾相连即可*/if(headk!=0)rectailj.next=headk;j=k;k+;rectailj.next=0;/*设置最后一个非空队列尾单元的后继是0*/for/*至此，rec中静态链表已经有序，将它复制到r中*/i=0;k=rec0.next;while(k!=0)ri+=reck.key;k=reck.next;free(tail);free(head);free(rec);return;三、外排序三、外排序K路平衡归并路平衡归并 K路归并：一次归并多个归并段的归并排序。它路归并：一次归并多个归并段的归并排序。它比二路归并效率更高比二

45、路归并效率更高 K路归并排序中的选择结构：路归并排序中的选择结构：堆堆 胜者树胜者树 败者树败者树RR01R02 R03R04R05R06R11R12R13R21R22331320910612R1R0R2R3R4归归并并的的结结果果152537381417182224401014209101512R1R0R2R3R46归归并并的的结结果果25373814171822244000142018101512R1R0R2R3R46,9归归并并的的结结果果253738141722244044142018141512R1R0R2R3R46,9,10归归并并的的结结果果25373817222440(1)胜胜

46、者者树树的的初初始始状状态态，R3首首单单元元是是最最小小值值(2)第第1次次选选择择，R1的的首首单单元元成成为为最最小小值值(3)第第2次次选选择择，R0的的首首单单元元成成为为最最小小值值(4)第第3次次选选择择，R4的的首首单单元元成成为为最最小小值值(1)败败者者树树的的初初始始状状态态，R3首首单单元元是是最最小小值值(2)第第1次次选选择择，R1的的首首单单元元成成为为最最小小值值(3)第第2次次选选择择，R0的的首首单单元元成成为为最最小小值值(4)第第3次次选选择择，R4的的首首单单元元成成为为最最小小值值102420910612R1R0R2R3R4归归并并的的结结果果152

47、5373814171822244030423209101512R1R0R2R3R46归归并并的的结结果果253738141718222440114232018101512R1R0R2R3R46,9归归并并的的结结果果2537381417222440010232018141512R1R0R2R3R46,9,10归归并并的的结结果果253738172224404三、外排序三、外排序置换选择排序置换选择排序 用于形成长度不等的初始归并段用于形成长度不等的初始归并段有序归并段有序归并段工作区（设工作区（设W=6）数据输入序列数据输入序列51,49,39,46,38,29,14,61,75,3,1,12

48、,15,3,63,2751,49,39,46,38,2914,61,75,3,1,12,15,3,63,272951,49,39,46,38,14,61,75,3,1,12,15,3,63,272951,49,39,46,38,141461,75,3,1,12,15,3,63,2729,3851,49,39,46,14,1461,75,3,1,12,15,3,63,2729,3851,49,39,46,61,141475,3,1,12,15,3,63,2729,38,3951,49,46,61,141475,3,1,12,15,3,63,2729,38,3951,49,75,46,61,141

49、43,1,12,15,3,63,2729,38,39,4651,49,75,61,14143,1,12,15,3,63,2729,38,39,4651,49,75,3,61,14141,12,15,3,63,2729,38,39,46,4951,75,3,61,14141,12,15,3,63,2729,38,39,46,4951,1,75,3,61,141412,15,3,63,2729,38,39,46,49,51,1,75,3,61,141412,15,3,63,2729,38,39,46,49,5112,1,75,3,61,141415,3,63,2729,38,39,46,49,51

50、,6112,1,75,3,141415,3,63,2729,38,39,46,49,51,6112,1,75,3,15,14143,63,2729,38,39,46,49,51,61,7512,1,3,15,14143,63,2729,38,39,46,49,51,61,7512,1,3,3,15,141463,27三、外排序三、外排序哈夫曼归并树哈夫曼归并树9523112185172624403212495931121851726243413124(a)(b)导航图导航图(1)排序排序基本概念基本概念内排序内排序外排序外排序插入排序插入排序交换排序交换排序选择排序选择排序索引排序索引排序计数