数据结构与算法之内排序37584

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,7 内排序,主要内容,内部排序/外部排序,稳定/不稳定排序,排序算法性能分析,内部排序算法,2,内排序,设,n,个记录的序列为 R,1, R,2, R,3, . . . , R,n,其相应的关键字序列为 K,1, K,2, K,3, . . . , K,n,若规定 1 , 2 , 3 , . . . , n 的一个排列 p,1, p,2, p,3, . . . , p,n,，使得相应的关键字满足如下非递减关系:,K,p, K,p, K,p, . . . K,p,1,2,3,n,则原序列变为一个按关键字有序的序列:,R,p, R,p, R,p, . . . , R,p,1,2,3,n, ,此操作过程称为,排序,。,排 序,3,内排序,内部排序:,指的是待排序记录存放在计算机,随机存储器,中进行的排序过程。,外部排序:,指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对,外存,进行访问的排序过程。,内部排序与外部排序,4,内排序,假设 K,i,= K,j,，且排序前序列中 R,i,领先于 R,j,；,若在排序后的序列中 R,i,仍领先于 R,j,，则称排序方法是,稳定的,。,若在排序后的序列中 R,j,仍领先于 R,i,，则称排序方法是,不稳定的,。,例，序列 3 15,8,8 6 9,若排序后得 3 6,8,8 9 15,稳定的,若排序后得 3 6 8,8,9 15,不稳定的,稳定排序与不稳定排序,5,内排序,排序的时间复杂性,排序过程主要是对记录的排序码进行,比较和记录的移动,过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。,当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的,空间复杂性、稳定性和简单性,等。,6,内排序,按照排序过程中所依据的原则的不同可以分类为:,插入排序,交换排序,选择排序,归并排序,基数排序,二叉排序树排序,内部排序,7,内排序,思想:,利用有序表的插入操作进行排序,有序表的插入:,将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。,例，序列 13 27 38 65 76 97,插入 49,13 27 38,49,65 76 97,插入排序直接插入排序,8,内排序,例，序列 49 38 65 97 76 13 27,初始，S = 49 ；,38,49 ,初始，令第,1,个元素作为初始有序表；,依次插入第,2,3, ,k,个元素构造新的有序表；,直至最后一个元素；, 38 49,65, 38 49 65,97, 38 49 65,76,97 ,13,38 49 65 76 97 , 13,27,38 49 65 76 97 ,直接插入排序算法主要应用,比较,和,移动,两种操作。,直接插入排序算法描述,9,内排序,void insertsort(ElemType R,int n),/待排序元素用一个数组R表示，数组有n个元素, for ( int i=1; i=0)& (tempRj), Rj+1=Rj; j-;, / 顺序比较和移动,Rj+1=temp;,10,内排序,直接插入排序的效率分析,从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。,从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。,C,min,=n-1 M,min,=2（n-1）,C,max,=1+2+n-1=（n,2,-n）/2,M,max,=3+4+n+1=（n,2,+3n-4）/2,C,ave,=（n,2,+n-2）/4,M,ave,=（n,2,+5n-6）/4,因此，直接插入排序的时间复杂度为O（n,2,）。,直接插入算法的元素移动是顺序的，该方法是稳定的。,11,内排序,插入排序,平均情况复杂度,对每个 i 值，考虑平均情况下需要多少次比较。为简化分析，假设所有的值是不相同的，对一个 i 和临时变量 x， x 有 i+1 个位置可能会去,0 1 2 .i-1 x=Ai,比较次数和插入位置的关系：i=6,A0 A1 A2 A3,A4 A5,x=A6,插入位置,6,5,4,3,2,1,0,比较次数,1,2,3,4,5,6,6,12,内排序,插入排序,平均情况复杂度,在对序列没有其它任何信息的条件下, x 到任何一个位置的概率都是1/(i+1). 这样, 对一个特定的值i , 需要的平均比较次数为:,把所有n-1次插入累加起来, 有:,13,内排序,由于直接插入排序算法利用了有序表的插入操作，故,顺序查找,操作可以替换为,折半(二分法)查找,操作。,例，序列 49 38 65 97 76 13 27,设已形成有序表 38 49 65 76 97 13,插入元素 13,折半插入排序,left,right,mid,right,mid,0 1 2 3 4 5,right, ,97,76,65,49,38,13,14,内排序,算法:,void BinaryInsertSort(ElemType R,int n), for(int i=1; in; i+) /共进行n-1次插入, int left=0,right=i-1;ElemType temp=Ri;,while(left=right), int middle=(left+right)/2; /取中点,if (temp=left;j-),Rj+1=Rj; /元素后移空出插入位,Rleft=temp;,15,内排序,折半插入效率分析,二分插入算法与直接插入算法相比，,需要辅助空间与直接插入排序基本一致；,时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，,两种方法的元素的移动次数相同，,因此二分插入排序的时间复杂度仍为O(n,2,)。,二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。,16,内排序,分析直接插入排序,1. 若待排序记录序列按关键字,基本有序,，则排序效率可大大提高；,2. 待排序记录总数越少，排序效率越高；,希尔(shell)排序,17,内排序,思想:,先将待排序记录序列分割成为若干子序列分别进行直接插入排序；,待整个序列中的记录基本有序后，再全体进行一次直接插入排序。,例，序列 49 38 65 97 76 13 27 48 55 4 19,第一趟排序,49 13 19,38 27,65 48,97 55,76 4,13 19 49,27 38,48 65,55 97,4 76,18,内排序,第二趟排序,13 19 49,27 38,48 65,55 97,4 76,13 55 38 76,27 4,65 49,48 19 97,13 38 55 76,4 27,49 65,19 48 97,第三趟排序,4 13 19 27,38,48 49,55 65 76,97,19,内排序,65,34,25,87,12,38,56,46,14,77,92,23,56,34,14,77,12,23,65,46,25,87,92,38,结果序列,d=6,56,34,14,77,12,23,65,46,25,87,92,38,56,12,14,65,34,23,77,46,25,87,92,38,结果序列,d=3,56,12,14,65,34,23,77,46,25,87,92,38,12,14,23,25,34,38,46,56,65,77,87,92,结果序列,d=1,(a),(b),(c),希尔排序的排序过程,0,1 2 3 4 5,6,7 8 9 10 11,0,1 2,3,4 5,6,7 8,9,10 11,20,内排序,希尔排序的算法,template ,void,ShellSort (T Vector, int arrSize ),T temp,;,int,gap = arrSize / 2,;,/gap,是子序列间隔,while,( gap != 0 ),/,循环,直到,gap,为零,for,(,int,i = gap,;,i = gap,;,j,-,= gap ),if,( temp Vectorj,-,gap ),Vectorj = Vectorj,-,gap,;,else break;,Vectorj = temp,;,gap = (,int,) ( gap / 2,),;,21,内排序,希尔排序效率分析,希尔排序的时间复杂性在O（nlog,2,n）和O（n,2,）之间，大致为O（n,1. 3,）。,（Flash动画演示）,希尔排序是不稳定的排序算法。,22,内排序,思想:,通过不断比较相邻元素大小，进行交换来实现排序。,首先将第一个元素与第二个元素比较大小，若为逆序，则交换；,然后比较第二个元素与第三个元素的大小，若为逆序，则交换；,. . .,直至比较第 n,-,1 个元素与第 n 个元素的大小，若为逆序，则交换；,第一趟排序:,结果:,关键字最大,的记录被交换至,最后,一个元素位置上。,交换排序冒泡排序,23,内排序,交换排序冒泡排序,优点,：,每趟结束时，不仅能挤出一个最大值到最后面位置(或者最小值到最前面位置)，,还能同时部分理顺其他元素,；一旦下趟没有交换发生，还可以,提前结束排序,。,24,内排序,例，序列 49 38 76 13 27,49 38 76 13 27,38,49,13,27,38 49,13 76,27 76,初始,第一趟排序后,最大值,13,49,27 49,次大值,第二趟排序后,38 13,27,13 27,13 38,27 38,第三趟排序后,第四趟排序后,25,内排序,冒泡排序的算法实现,。,void Bubblesort(ElemType R,int n), int flag=1; /当flag为0则停止排序,for (int i=1; i=i; j-),if (RjRj-1) /发生逆序,ElemType t=Rj;,Rj=Rj-1;,Rj-1=t;,flag=1; /交换，并标记发生了交换,if(flag=0)return; ,26,内排序,冒泡排序的效率分析,最好情况：若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；,最坏情形：,初始排列逆序，算法要执行,n,-1趟排序，第,i,趟(1,i,n,) 做了,n- i,次关键码比较，执行了3(,n-i ),次数据元素交换。此时的比较总次数和记录移动次数为：,因此冒泡排序算法的时间复杂度为O（n,2,）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。,因为冒泡排序算法只进行元素间的顺序移动，所以是一个,稳定的,算法。,27,内排序,冒泡排序的一种改进算法。,思想:,以,首记录,作为,轴记录,，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。(小值记录在前、大值记录在后),轴记录,将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。,直至整个序列有序。,交换排序快速排序,28,内排序,快排序（Quick Sort),快排序算法思想,取序列的一个元素作为,轴,，利用这个轴把序列分成三段：左段，中段(轴),和,右段, 使左段中各元素都小于等于轴，右段中各元素都大于等于轴。(这个过程称做对序列,分割,或,划分,),左段,和右段的元素可以独立排序, 将排好序的三段合并到一起即可,上面的过程可以递归地执行，直到每段的长度为1,29,内排序,快排序（Quick Sort),快速排序实例,快排序算法思想,30,内排序,快排序（Quick Sort),快排序-分割过程,快排序是一个分治算法（也是第一个）,快排序的关键过程是每次递归的分割过程,分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边,分割算法：,用临时变量对轴备份,取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high,移动两个指针,首先从high所指的位置向左搜索，找到第一个小于轴的元素, 把这个元素放在low的位置,再从low开始向右，找到第一个大于轴的元素，把它放在high的位置,31,内排序,快排序（Quick Sort),快排序-分割过程,分割算法：,重复上述过程，直到low=high，,把轴放在low所指的位置,这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边,32,内排序,快排序（Quick Sort),快排序-分割过程,38 65 97 76 13 27 49,49,low,high,pivot = 49,0 1 2 3 4 5 6 7,high,38 65 97 76 13 49,27,low,27,38 97 76 13 49,65,high,27,38 97 76,65,49,13,low,27,38,13,76,65,49,97,high,49,33,内排序,快排序（Quick Sort),快排序-分割过程,int Partition(T Array, int low, int high),T pivot = Arraylow;,while(low high),while(low = pivot),high -;,Arraylow = Arrayhigh;,while(low high & Arraylow = pivot),low+;,Arrayhigh = Arraylow;,Arraylow = pivot;,return low;,34,内排序,快排序（Quick Sort),快排序-算法,快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1,0 1 2 3 4 5 6 7,49,38 65 97 76 13 27 49,76 97 65 49,27 38 13,49,49,13,38,27,49 65,97,76,13 17 38 49 76 97,49,65,35,内排序,快排序（Quick Sort),快排序-算法,void QuickSort(T Array, int low, int high),int PivotLocation;,if(low high),PivotLocation = Partition(Array, low, high);,QuickSort(Array, low, PivotLocation-1);,QuickSort(Array, PivotLocation+1, high);,36,内排序,3快速排序的效率分析,若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log,2,nhlog,2,n+1 ，所以总的比较次数不会超过(n+1) log,2,n。因此，快速排序的最好时间复杂度应为O（nlog,2,n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog,2,n）。,若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1in）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n,2,+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n,2,)。,快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log,2,n），最坏的空间复杂度为O(n)。,快速排序是一种不稳定的排序方法。 (举例：6,7,5,2,5,8),37,内排序,思考题,请给出在最坏情况下只需7次元素比较的5个元素的排序算法。,2. 请给出一个有效的对n个元素进行排序的算法，使得所有负元素位于非负元素之前。,3. 请给出一个有效的对n个正整数进行排序的算法，使得所有偶数位于奇数之前。,38,内排序,思想:,每一趟都选出一个最大或最小的元素，并放在合适的位置。,直接选择排序,树形选择排序,堆排序,选择排序,39,内排序,思想:,第 1 趟选择:,从,1n,个记录中选择关键字最小的记录，并和第,1,个记录交换。,第 2 趟选择:,从,2n,个记录中选择关键字最小的记录，并和第,2,个记录交换。,第n,-,1趟选择:,从,n,-,1n,个记录中选择关键字最小的记录，并和第,n,-,1,个记录交换。,. . .,直接选择排序,40,内排序,例，序列 49 38 97 65 76,第 1 趟选择:,min,38,49 97 65 76,第 2 趟选择:,min,38,49,97 65 76,第 3 趟选择:,min,38,49,65,97 76,第 4 趟选择:,min,38,49,65,76,97,41,内排序,直接选择排序的算法,template ,void,SelectSort ( T Vector, int CurrentSize),for,(,int i,= 0,; i, CurrentSize,-,1,;,i,+,),int,k = i,;,/,选择具有最小排序码的对象,for,(,int,j = i+1,;,j CurrentSize,;,j+),if,( Vectorj,Vectork ),k = j,;,/,当前具最小排序码的对象,if,( k != i ),/,对换到第,i,个位置,Swap ( Vectori,Vectork,),;,42,内排序,直接选择排序复杂度分析,时间效率： O(n,2,)虽移动次数较少，但比较次数仍多。,空间效率：O（1）没有附加单元（仅用到1个temp),算法的稳定性：不稳定,（举例：6，2，,6,，3）,43,内排序,选择排序的主要操作是进行关键字间的,比较,。,在 n 个关键字中选出最小值，至少需要 n,-,1 次比较,。,在剩余的 n,-,1 个关键字中选出最小值，至少需要 n,-,2 次比较,？,如果能利用前 n,-,1 次比较所得信息，可以减少后面选择的比较次数。,体育比赛中的锦标赛:,直接选择排序分析,44,内排序,例，8 名运动员要决出 冠、亚、季军。,按简单选择排序需要比赛,7+6+5 = 18,场。,若能够利用以前的比赛结果，比赛场次实际可以减少为,11,场。,前提:,若 甲 胜 乙 ，乙 胜 丙 ，则 甲 必能胜 丙 。,Zhao,Cha,Liu,Bao,Diao,Yang,Xue,Wang,Bao,Bao,Diao,Cha,Bao,Diao,Wang,冠军,45,内排序,如何求 亚军？,Zhao,Cha,Liu,Diao,Yang,Xue,Wang,Cha,Diao,Cha,亚军,可以利用前面的比赛结果！,Cha,Liu,Diao,Wang,46,内排序,如何求 季军？,Zhao,Liu,Diao,Yang,Xue,Wang,Liu,Diao,Diao,季军,同样可以利用前面的比赛结果！,Liu,Diao,Wang,Zhao,47,内排序,又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。,例，序列 49 38 65 97 76 13 27 50,第一趟选择,13,38,13,49,38,65,97,76,13,27,50,38,65,13,27,最小值,树形选择排序,48,内排序,第二趟选择,27,38,27,49,38,65,97,76,27,50,38,65,76,27,次小值,第三趟选择,38,38,50,49,38,65,97,76,50,38,65,76,50,次次小值,49,38,65,97,76,13,27,50,49,38,65,97,76,27,50,缺点:,需要大量辅助存储空间,49,内排序,堆:,一棵完全二叉树，任一个非终端结点的值均小于等于(或大于等于)其左、右儿子结点的值。,例，,12,85,47,30,53,36,24,91,96,38,11,9,83,24,根结点为最小值,根结点为最大值,堆排序,50,内排序,2. 把这棵普通的完全二叉树改造成堆，便可获取,最小值,；,思想:,3. 输出最小值 ；,4. 删除根结点，继续改造剩余树成堆，便可获取,次小值,；,5. 输出次小值 ；,6. 重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序 。,1. 将序列构造成一棵完全二叉树 ；,51,内排序,例，序列 49 38 65 97 76 13 27 50,1. 按顺序依次构造成完全二叉树的结点；,49,38,65,97,76,13,27,50,2. 把完全二叉树改造成,堆,；,从下向上，父子交换；,50,97,13,65,13,49,49,27,3. 取得最小值,13,4. 删除,13,，重新改造成新堆；,13,97,27,97,97,49,5. 取得次小值,27,；,6. 删除,27,，重新改造成新堆；,97,27,97,38,97,50,7. 取得次次小值,38,；,52,内排序,算法分析,时间效率：,O,(,n,log,2,n,)。,因为整个排序过程中需要调用,n,-1次堆顶点的调整，而每次堆排序算法本身耗时为,log,2,n,；,空间效率：,O(1)。,仅在交换记录时用到一个临时变量temp。,稳定性：,不稳定。,优点：,对小文件效果不明显，但对大文件有效。,53,内排序,归并排序（Merge Sort),归并-合并两个有序的序列,假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2),方法很简单：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并， 其复杂度为O(n),54,内排序,归并排序（Merge Sort),归并-合并两个有序的序列,A: 1 3 8 9 11,B: 2 5 7 10 13,C:,1,2,3,5,7,8 9,10,11,13,55,内排序,归并排序（Merge Sort),归并-合并两个有序的序列,void merge(T A, int Alen, T B, int Blen, T C),int i=0,j=0,k=0;,while(i Alen & j Blen),if(Ai Bj),Ck+ = Ai+;,else,Ck+ = Bj+;,while(i Alen),Ck+ = Ai+;,while(j b和ab),如果以每次比较作为节点，则每个以比较为基础的排序算法都可以用一个二叉树来表示，其中一个中间节点表示一次比较，叶子节点表示排序的一种结果，这样的二叉树称为,判定树,或,决策树,举例：比如有一个序列a, b, c(a,b,c互不相等） ，下列算法：,先比较a和b, 再比较a和c，最后比较b和c,可以用下面的判定树表示,以比较为基础的排序算法的下界,62,内排序,ab?,yes,ac?,yes,bc?,yes,abc,acb,no,no,no,cab,ac?,yes,bac,no,bc?,yes,bca,cba,no,以比较为基础的排序算法的下界,63,内排序,假设输入为a,b,c, acb, 则算法执行经过的路线为(ab)(ac)(bc)，需要3次比较,假设输入为a,b,c, bac, 则算法执行经过的路线为(ab)(ac) 需要2次比较,任何以比较为基础的排序算法都可以表示为一棵决策树,树的形状和大小表示的是排序算法的功能和需要排序的元素个数,树的高度表示了算法的运行时间,任何排序决策树都有n!个叶子,以比较为基础的排序算法的下界,64,内排序,根据数据结构中关于二叉树的性质，有：,最坏情况：任何排序算法至少要做,次比较,平均情况：任何排序算法的平均比较次数的下界是,结论：具有,O,(,n,lg,n,)复杂度的比较排序算法在渐进意义下是最优的算法,以比较为基础的排序算法的下界,65,内排序,基于分配的排序,桶式排序,基数排序,66,内排序,桶式排序,事先知道序列中的记录都位于某个小区间段,0,，,m),内将具有相同值的记录都分配到同一个桶中，然后依次按照编号从桶中取出记录，组成一个有序序列。,67,内排序,桶式排序,m=10,初始序列：3，2，4，8，7，1，6，4，9，8，7,出现次数：0，1，1，1，2，0，1，2，2，1,开始位置：0，1，2，3，5，5，6，8，10，11,排序结果：1，2，3，4，4，6，7，7，8，8，9,68,内排序,桶式排序算法分析,数组长度为,n,所有记录区间,0,m),上,时间代价：,统计计数时：,(n+m),输出有序序列时循环,n,次,总的时间代价为,(m+n),适用于,m,相对于,n,很小的情况,空间代价：,m,个计数器，长度为,n,的临时数组，,(m+n),稳定,69,内排序,桶式排序和基数排序,桶式排序只适合,m,很小的情况。当,m,很大时，可以将一个记录的值即排序码拆分为多个部分来进行比较,基数排序,70,内排序,是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。,1. 多关键字排序,扑克牌问题 :,已知扑克牌中52张牌面的次序关系定义为:,花色:,面值:,2 3 A,. . .,例，,8,3,花色优先级更高，为主关键字，面值为次关键字,基数排序,71,内排序,2. 52张牌排序方法 :,最高位优先法(MSDF) :,先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；,然后分别对每一堆按“面值”大小整理有序。,最低位优先法(LSDF) :,先按不同“面值”分成 13 堆 ；,然后将这 13 堆牌自小至大叠在一起( 2 , 3 , . . . , A ) ；,然后将这付牌整个颠倒过来再重新按不同的“花色”分成 4 堆 ；,最后将这 4 堆牌按自小至大的次序合在一起 。,收集,分配,72,内排序,3. 基数排序,基数排序就是借助于“,分配,”和“,收集,”两种操作实现对单逻辑关键字的排序。,首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。,其次，利用 LSDF 法实现对若干关键字的排序。,例，若关键字是数值，且值域为 0K999 ，,故可以将,K,看作是由 3 个关键字,K,0,K,1,K,2,组成，,例，,603,是由,6 0 3,组成。,73,内排序,例，序列,278 109 063 930 589 184 505 269 008 083,第一趟分配,0 1 2 3 4 5 6 7 8 9,27,8,10,9,06,3,93,0,58,9,18,4,50,5,26,9,00,8,08,3,第一趟收集,930,063 083,184,505,278 008,109 589 269,第二趟分配,0 1 2 3 4 5 6 7 8 9,9,3,0,0,6,3,0,8,3,1,8,4,5,0,5,2,7,8,0,0,8,1,0,9,5,8,9,2,6,9,第二趟收集,505 008 109,930,063 269,278,083 184 589,74,内排序,第二趟收集,505 008 109,930,063 269,278,083 184 589,第三趟分配,0 1 2 3 4 5 6 7 8 9,5,05,0,08,1,09,9,30,0,63,2,69,2,78,0,83,1,84,5,89,第三趟收集,008 063 083,109 184,269 278,505 589,930,75,内排序,链式存储,在基于链式队列的基数排序算法中，可以把d个队列设计成一个队列数组（设队列数组名为tub），队列数组的每个元素中包括两个域： front域和rear域。front域用于指示队头，rear域用于指示队尾。当第i（i=0,1,2,d-1）个队列中有数据元素要放入时，就在队列数组的相应元素tubi中的队尾位置插入一个结点。,.,.,rear,front,data,next,0,1,2,d-1,.,.,.,tub,76,内排序,基数排序算法分析,特点：不用比较和移动，改用分配和收集，时间效率高！,时间复杂度为：,O,(,mn,),空间复杂度：,O,(,n,),稳定性：稳定(一直前后有序)。,77,内排序,中序遍历可实现二叉搜索树结点的有序化,13,8,5,23,18,37,9,5 8 9 13 18 23 37,? 如何实现自大到小排列,二叉树排序,78,内排序,排序方法,最好时 间,平均时间,最坏时间,辅助空间,稳定性,直接插入排序,O,(,n,),O,(,n,2,),O,(,n,2,),O,(1),稳定,希尔排序,O,(,n,1.3,),O,(1),不稳定,直接选择排序,O,(,n,2,),O,(,n,2,),O,(,n,2,),O,(1),不稳定,堆排序,O,(,n,log,2,n,),O,(,n,log,2,n,),O,(,n,log,2,n,),O,(1),不稳定,冒泡排序,O,(,n,),O,(,n,2,),O,(,n,2,),O,(1),稳定,快速排序,O,(,n,log,2,n,),O,(,n,log,2,n,),O,(,n,2,),O,(log,2,n,),不稳定,归并排序,O,(,n,log,2,n,),O,(,n,log,2,n,),O,(,n,log,2,n),O,(,n,),稳定,基数排序（基于链式队列）,O,(,mn,),O,(,mn,),O,(,mn,),O,(,n,),稳定,基数排序（基于顺序队列）,O,(,mn,),O,(,mn,),O,(,mn,),O,(,mn,),稳定,习题九,性能比较,79,内排序,各种内排序方法的选择,1从时间复杂度选择,对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。,2从空间复杂度选择,尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log,2,n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。,3一般选择规则,（1）,当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。,80,内排序,（2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。,（3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。,（4,),当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。,(5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。,81,内排序,各种排序方法的比较,82,内排序,课堂练习,对于一组记录的排序码为(465，792，562，383，401，845，502，423)，写出基数排序（低位优先）进行一趟分配与回收后的结果。,83,内排序,上机作业,实现各种排序算法:,插入排序,冒泡排序,shell排序,选择排序,快速排序,归并排序,堆排序,基数排序,84,内排序,序列 8 , 3 , 10 , 13 , 25 , 18 , 6 , 4,对上述序列使用直接插入排序、希尔排序（d,1,=4；d,2,=2;d,3,=1;）、快速排序、堆排序、归并排序、基数排序（低位优先）进行排序的过程。,书面作业（下周二交）,85,内排序,后续内容,第九章 检索,顺序,二分,散列,86,内排序,演讲完毕，谢谢观看！,