《VC编程教程 第9章 排序.ppt》由会员分享，可在线阅读，更多相关《VC编程教程 第9章 排序.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章 排序本章学习要求本章学习要求掌握：排序的基本概念和相关术语。掌握：插入排序的基本思想，直接插入排序算法、折半插入排序算法以及希尔排序算法的实现过程和实现算法。并了解插入排序算法的时间效率和空间效率。掌握：交换排序的基本思想，冒泡排序算法、快速排序算法的实现过程和实现算法。并了解冒泡排序和快速排序的算法评价。掌握：选择排序的基本思想，简单选择排序以及堆排序的实现算法和算法评价。掌握：归并排序的基本思想和2路归并的实现算法。默认的排序数据结构：待排序的记录采用顺序存储，待排序记录的定义为：#defineMAXSIZE100/*假定顺序表的最大长度为100*/typedefintKeyTyp
2、e；/*假定关键字类型为整数类型*/typedefstructKeyTypekey；/*关键字项*/OtherTypeother；/*其他项*/DataType；/*数据元素类型*/typedefstructDataTyperMAXSIZE+1；/*r0闲置或充闲置或充当哨兵当哨兵*/intlength；/*顺序表长度*/SqList；/*顺序表类型*/9.1 基本概念排序定义将一个数据元素（或记录）的任意序列，重新排列成一个按关键码有序的序列叫排序分类v按待排序记录所在位置l内部排序：待排序记录存放在内存l外部排序：排序过程中需对外存进行访问的排序排序的稳定性v若相同关键码元素间的位置关系，
3、排序前与排序后保持一致，称此排序方法是稳定的，否则为不稳定的排序基本操作v比较两个关键字大小v将记录从一个位置移动到另一个位置排序方法：v内排序(本章讨论的方法):待排序的记录在排序过程中全部存放在内存l插入排序：直接插入排序、折半插入排序、表插入排序、希尔排序l交换排序：冒泡排序、快速排序l选择排序：简单选择排序、树形选择排序、堆排序l归并排序：2-路归并排序l基数排序：多关键码排序、链式基数排序v外排序：排序过程中需要使用外存。l多路平衡归并按排序所需工作量v简单的排序方法：T(n)=O(n)v先进的排序方法：T(n)=O(logn)v基数排序：T(n)=O(d.n)评价排序算法好坏的标准
4、主要有两条第一是执行算法所需的时间；第二是执行算法所需要的附加空间；另外算法本身的复杂程度也是考虑的一个因素。由于排序是经常使用的一种运算，因此，排序的时间开销是算法好坏的最重要的标志。而排序的时间开销又可以用算法执行中的比较和移动次数来衡量。同时排序的稳定性有时也要考虑。9.2 插入排序9.2.1直接插入排序vv假设待排序的假设待排序的n n个记录个记录R0,R1,Rn-1R0,R1,Rn-1存放在数存放在数组中，组中，直接插入法直接插入法在插入记录在插入记录Ri(iRi(i=1,2n-1)=1,2n-1)时，时，记录集合被划分为两个区间记录集合被划分为两个区间R0R0，Ri-1Ri-1和和
5、 RiRi，Rn-1Rn-1，其中，前一个子区间已经排好序，后一个，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码子区间是当前未排序的部分，将排序码KiKi与与Ki-1Ki-1，Ki-2Ki-2，K0K0依次比较，找出应该插入的位置，依次比较，找出应该插入的位置，将记录将记录RiRi插入，原位置的记录向后顺移。插入，原位置的记录向后顺移。直接插入直接插入排序排序采用采用顺序存储结构顺序存储结构。基本思想：每次将一个待排序的记录，按其关键码大小插入到前面已经排好序的子序列的适当位置，直到全部记录插入完成。例49 38 65 97 76 13 27i=2 38 (38 49
6、)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：v算法描述for(i=2;i=n;i+)设置监视哨；寻找插入位置；移动元素；插入；可以边寻找插入位置边移动元素。v算法评价l时间复杂度u最好情况：若待排序记录按关键字从小到大排列(正序)Y
7、关键字比较次数：Y记录移动次数：u最坏情况：若待排序记录按关键字从大到小排列(逆序)Y关键字比较次数：Y记录移动次数：u若待排序记录是随机的，取平均值Y关键字比较次数：Y记录移动次数：T(n)=O(n)l空间复杂度：S(n)=O(1)直接插入排序是稳定的排序算法直接插入排序是稳定的排序算法9.2.2折半插入排序v排序过程：用折半查找方法确定插入位置的排序叫例i=1 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85)20.i=8 20 (6 13 30 39 42 70 85)20lhm
8、i=8 20 (6 13 30 39 42 70 85)20lhmi=8 20 (6 13 30 39 42 70 85)20ljmhi=8 20 (6 13 30 39 42 70 85)20lhi=8 20 (6 13 20 30 39 42 70 85)for(i=2;i=n;i+)设置监视哨；寻找插入位置；移动元素；插入；voidBinaryInsertSort(SqList*s)/*对顺序表S作折半插入排序*/intlow,high,mid;for(i=2；ilength；i+)S-r0=S-ri；/*保存待插入元素*/low=1；high=i-1；/*设置初始区间*/while(l
9、owr0.keyS-rmid.key)low=mid+1；/*插入位置在高半区中*/elsehigh=mid-1；/*插入位置在低半区中*/*while*/for(j=i-1；j=high+1；j-)/*high+1为插入位置*/S-rj+1=S-rj；/*后移元素，留出插入空位*/S-rhigh+1=S-r0；/*将元素插入*/*for*/*BinaryInsertSort*/效率分析：教材有误！教材有误！否则排序不否则排序不稳定！稳定！v算法描述2.二分法插入排序二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数，插入第i个记录时，其比较次数最多为n个记录排序的总比较次数
10、为：移动记录的次数和直接插入排序相同，故时间复杂度仍为O(n2)。二分法插入排序是一个稳定的排序方法/注意保证注意保证if(S-r0.keyS-rmid.key)low=mid+1；算法的辅助空间为O(1)注：推导过程略注：推导过程略可以参考北京大学教材可以参考北京大学教材9.2.4希尔排序(缩小增量法)shell排序又称缩小增量排序(Diminishing Increment Sort)。先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序“时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。shell排序的一个特点是：子序列的构成不是简单“逐
11、段分割”，而是将相隔某个增量的记录组成一个子序列。取d3=1三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始：49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13 27 48 55 4 49 38 65 97 76算法描述一趟希尔排序算法描述：voidShellInser
12、t(datatypeR,intn,intdk)inti,j;for(i=dk+1;i0&r0.keyrj.key)rj+dk=rj;j=j-dk;rj+dk=r0;直接插入算法描述：voidD_InsertSort(datatypeR,intninti,j;for(i=2;i=n;i+)r0.key=ri.key;j=i-1;while(r0.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上v对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置v
13、重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止例49 38 65 97 76 13 27 30初始关键字38 49 65 76 13 27 30 97第一趟38 49 65 13 27 30 76第二趟38 49 13 27 30 65第三趟38 13 27 30 49第四趟13 27 30 38第五趟13 27 30第六趟38497697139727973097137676762730136527653065131349493049273827383038for(i=1;i=n-1;i+)for(j=1;jn-i;j+)两两比较交换；for(i=1;i=n-1;i+)sw
14、ap=0;for(j=1;jrj+1.key)交换；swap=1;if(swap=0)break;v算法评价l时间复杂度u最好情况（正序）Y比较次数：n-1Y移动次数：0u最坏情况（逆序）Y比较次数：Y移动次数：l空间复杂度：S(n)=O(1)T(n)=O(n)起泡排序是稳定的：S-rj.keyrj-1.key交换改成=将变成不稳定的9.3.2快速排序v基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续使用该方法排序，以达到整个序列有序v排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp
15、=rs，x=rp.keyl初始时令low=s,high=tl首先从high所指位置向前搜索第一个关键字小于x的记录，并和rp交换l再从low所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换l重复上述两步，直至low=high为止l再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止例初始关键字：49 38 65 97 76 13 27 50 lowhigh支点49 27 38 65 97 76 13 27 50 lowhighhighlowlowhigh 27 38 65 97 76 13 65 50 27 38 13 97 76 13 65 50 lowhigh 27
16、 38 13 97 76 97 65 50 low high 27 38 13 97 76 97 65 50 lowhigh 完成一趟排序：(27 38 13)49 (76 97 65 50)v总结：1）所有的比较都跟支点进行；2）比较的元素位置不断与支点靠近，最终重合时一趟快排结束。3）一趟快排结束时，支点找到了它的最终位置。IntQuickSort1(datatypeR,ints,intt)确定支点；设置low、high起始位置；while(rowlow&rhigh.keylow&r0.keyrlow.key时与支点交换；returnlow;intQuickSort1(SqList*s,i
17、ntlow,inthigh)KeyTypepivotkey;S-r0=S-rlow;/*以子表的第一个记录作为轴值记录*/pivotkey=S-rlow.key;/*取轴值记录关键字*/while(lowhigh)/*从表的两端交替地向中间扫描*/while(lowrhigh.key=pivotkey)high-;S-rlow=S-rhigh;/*将比轴值记录小的交换到低端*/While(lowrlow.keyrhigh=S-rlow;/*将比轴值记录大的交换到高端*/S-rlow=S-r0;/*轴值（支点）记录到位*/returnlow;/*返回轴值（支点）记录所在位置*/一趟快速排序，供递
18、归调用voidQuickSort(SqList*s,intlow,inthigh)/*递归形式的快速排序*/*对顺序表S中的子序列rlowhigh作快速排序*/intpivotloc;if(lowhigh)pivotloc=QuickSort1(S,low,high);/*将待排序序列一分为二*/QuickSort(S,low,pivotloc-1);/*对小于轴值序列实现递归排序*/QuickSort(S,pivotloc+1,high);/*对大于轴值序列实现递归排序效率分析最坏情况：是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分
19、前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为最好情况：最好情况：每次所取的pivotkey是当前无序区的“中值”，划分的结果是pivotkey的左右两个无序子区的长度大致相等设C(n)表示长度为n的序列快速排序的比较次数，它等于长度为n的无序区进行比较次数n-1，加上对划分所得的左右两个无序子区进行快速排序所需的比较次数，假设文件长度n=2k，k=log2n，有：快速排序不快速排序不稳定稳定返回返回 为了改善最坏情况下的时间性能，可采用“三者取中”的规则，即在每一趟划分前，首先比较Rl.key、Rr.key和R.key的大小，取中间的记录
20、与Rl交换。快速排序的平均时间复杂度是T(n)=O(nlog2n)。算法需要一个栈空间实现递归。栈的大小取决于递归调用的深度，最多不超过n，若每次都选较大的部分进栈，处理较短的部分，则递归深度最多不超过log2n，所以快速排序的辅助空间为S(n)=O(log2n)。快速排序是不稳定的。每一趟从待排序列中选取一个关键字最小的记录，即第一趟从n个记录中选取关键字最小的记录，第二趟从剩下的n-1个记录中选取关键字次小的记录，直到整个序列的记录选完为止。这样根据选取记录的顺序，可得到按关键字有序的序列1.简单选择排序2.堆排序9.4 选择排序9.4.1简单选择排序v排序过程l首先通过n-1次关键字比较
21、，从n个记录中找出关键字最小的记录，将它与第一个记录交换l再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换l重复上述操作，共进行n-1趟排序后，排序结束例初始：49 38 65 97 76 13 27 一趟：13 38 65 97 76 49 27 二趟：13 27 65 97 76 49 38 三趟：13 27 38 97 76 49 65 四趟：13 27 38 49 76 97 65 五趟：13 27 38 49 65 97 76 六趟：13 27 38 49 65 76 97 排序结束：13 27 38 49 65 76 97for(i=1;i=n-
22、1;i+)k=in中最小元素位置；Ri与Rk交换；voidSelectSort(SqList*s)for(i=1；ilength；i+)/*作S-length-1趟选取*/for(j=i+1，t=i；jlength；j+)/*在i开始的length-i+1条待排序记录中选关键字最小的记录*/if(S-rt.keyS-rj.key)t=j；/*t中存放关键字最小的记录下标*/tmp=S-rt;S-rt=S-ri;S-ri=tmp;/*关键字最小的记录与第i条记录交换*/效率分析v算法评价l时间复杂度u记录移动次数Y最好情况：0Y最坏情况：3(n-1)u比较次数：l空间复杂度：S(n)=O(1)T
23、(n)=O(n)简单选择排序是不稳定的简单选择排序是不稳定的9.4.3堆排序v堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,.n/2)Kik2ikik 2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值小根堆大根堆v堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一
24、个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫v堆排序需解决的两个问题：l如何由一个无序序列建成一个堆？l如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？v第二个问题解决方法筛选筛选l方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例13273849657650979727384965765013输出：13第一次筛选筛选算法：VoidHeapAdjust(datatypeR,ints,intt)rc=Rs;i=s
25、;j=R2*i与R2*i+1中较小值的序号;If(Ri.data.keyRj.data.key)筛选结束；elseRi=Rj;i=j;While(i1;i-)R1与Ri交换；HeapAdjust(R,1,i-1);v第一个问题建堆解决方法l方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097建堆算法：
26、for(i=n/2;i0;i-)HeapAdjust(R,i,n);堆排序算法：voidHeapSort(datatypeR,intn)建堆;n-1次筛选；for(i=n;i0;i-)输出Ri数据；C实现voidHeapAdjust(SqList*s，intn，intm)/*S-rnm中的记录关键字除rn外均满足堆的定义，本函数将对第n个结点为根的子树筛选，使其成为大顶堆*/inti,j;DataTyperc;rc=S-rn；i=n;for(j=2*i；j=m；j=j*2)/*沿关键字较大的孩子结点向下筛选*/if(jrj.keyrj+1.key)j=j+1；/*为关键字较大的元素下标*/if
27、(rc.keyS-rj.key)break；/*rc应插入在位置i上*/S-ri=S-rj；i=j；/*使i结点满足堆定义*/S-ri=rc；/*插入*/voidHeapSort(SqList*s)inti;for(i=S-length/2；i0；i-)/从第一个分支节点开始建堆/*将r1.length建成堆*/HeapAdjust(S，i，S-length)；for(i=S-length；i1；i-)S-r1S-ri；/*堆顶与堆底元素交换,将最大元素移到后面*/HeapAdjust(S，1，i-1)；/*将r1.i-1重新调整为堆*/堆排序的效率分析堆排序适合记录很多的情形，它的时间复杂度
28、为O(nlog2n)。堆排序中初始建堆虽然时间复杂度为O(n)，但每次调整后面的花费时间很少堆排序算法中增加了一个辅助空间，辅助空间为O(1)。堆排序时间效率基本与待排序记录的初始状态无关堆排序是不稳定的堆排序是不稳定的返回返回 归并的含义是将两个或两个以上的有序表合并成一个有序表。利用归并的思想就可以实现排序。假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。9.5 9.5 归并排序归并排序例题初始序列为25,57,48,37,1
29、2,82,75,29,16，请用二路归并排序法排序。初始排序码 25 5748 37 12 82 75 29 16 /第一趟归并后25 57 37 48 12 82 29 75 16 /第二趟归并后25 37 48 57 12 29 75 82 16 /第三趟归并后12 25 29 37 48 57 75 82 16 /第四趟归并后12 16 25 29 37 48 57 75 82排序后的结果为12,16,25,29,37,48,57,75,82voidmerge(datatypeR,datatypeR1,ints,intm,intt)/*Rsm和Rm+1t分别有序*/i=s;j=m+1;k
30、=s;while(i=m&jRj.key)R1k=Rj;k+;j+;elseR1k=Ri;k+;i+;whiel(i=m)R1k=Ri;k+;i+;whiel(j=t)R1k=Rj;k+;j+;/*将有序的Rsm和Rm+1t归并为有序的R1st*/2-路归并排序v排序过程l设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1l两两合并，得到n/2个长度为2或1的有序子序列l再两两合并，如此重复，直至得到一个长度为n的有序序列为止例初始关键字：49 38 65 97 76 13 27 12 06一趟归并后：38 49 65 97 13 76 12 27 06二趟归并后：38 49
31、 65 97 12 13 27 76 06三趟归并后：06 13 27 38 49 65 76 97子表长为len的某一趟归并算法：voidmergepass(datatypeR,datatypeR1,intlen,intn)等长子表的合并；if（还剩余两个子表）不等长的两个子表合并；elseR中剩余元素复制到R1；子表长为len的某一趟归并算法：voidmergepass(datatypeR,datatypeR1,intlen,intn)/*等长子表的合并*/s=1;m=s+len-1;t=s+2*len-1;while(t=n)merge(R,R1,s,m,t);s=s+2*len;m=s
32、+len-1;t=s+2*len-1;if（mn）merge(R,R1,s,m,n);/*不等长的两个子表合并*/elsewhile(s=n)R1s=Rs;s+;/*R中剩余元素复制到R1；*/归并算法：voidmergesort(datatypeR,intn)intlen=1;while(lenn)mergepass(R,R1,len,n);len=2*len;mergepass(R1,R,len,n);len=2*len;v2-路归并的递归算法：voidmsort(datatypeR,datatypeR1,ints,intt)if(s=t)R1s=Rs;return;m=(s+t)/2;m
33、sort(R,R1,s,m);msort(R,R1,m+1,t);merge(R1,R,s,m,t);Voidmergesort(datatypeR,intn)datatypeR1MAXSIZE;msort(R,R1,1,n);算法评价对n个元素的归并排序，两两过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n次，故时间复杂度为O(nlog2n)。归并排序在最好和最坏情况下的时间复杂度都为O(nlog2n)空间复杂度:需要一个与待排记录等量的辅助空间，空间复杂度为O(n)。归并排序是稳定的排序。返回返回v几种内排序方法的比较排序方法 平
34、均时间性能最好时间性能最坏时间性能辅助存储空间稳定性直接插入 O(n2)O(n)O(n2)O(1)稳定希尔O(n1.3)O(1)不稳定冒泡O(n2)O(n)O(n2)O(1)稳定简单选择 O(n2)O(n)O(n2)O(1)不稳定快排O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定堆O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定小结排序是一般数据查找的前提步骤。排序可以分为交换、插入、选择、归并等多种排序方式，各种方式有各自的特点。（1）平均时间性能：以快速排序法最佳，但最坏情况下不
35、如堆排序和归并排序；在n较大时，归并排序比堆排序快，但所需辅助空间最多。（2）简单排序以直接插入排序最简单，当下列中记录“基本有序“或n值较小时，是最佳的排序方法。因此常和其他排序方法结合使用。（3）从稳定性来看，大部分时间复杂度为O(n2)的简单排序法都是稳定的。然而，快速排序、堆排序和希尔排序等时间性能较好的排序都是不稳定的。一般来说，排序过程中的比较是在相邻的两个记录关键字之间进行的排序方法是稳定的。大多数情况下排序是按记录的主关键字进行的，则所有的排序方法是否稳定无关紧要。当排序是按记录的次关键字进行时，则应根据问题所需慎重选择。本章讨论的大多数算法是在顺序存储结构上进行的，因此在排序
36、过程中要进行大量的记录的移动。当记录很大（即每个记录所占的空间很大）时，记录移动所耗费的时间也很多，此时可采用静态链表作存储结构，如表插入排序，链式基数排序，以修改指针代替移动记录。但有些方法如快速排序法是无法实现表排序的，在这种情况下，可以进行“地址排序”，即另设一个向量指示需要记录，同时在排序过程中不移动记录而移动地址向量中相应分量的内容。9.6基数排序9.6.1多关键字排序v定义：例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”v多关键字排序方法l最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成
37、若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列l最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列lMSD与LSD不同特点u按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序u按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序9.6.2链式基数排序v基数排序：将关键
38、码拆分为若干项，每项作为一个“关键码”，借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。v基：关键码可能出现的符号个数。l例取数字为关键码的基为10，取字母为关键码的基为26v链式基数排序：用链表作存储结构的基数排序v链式基数排序步骤l设置10个队列，fi和ei分别为第i个队列的头指针和尾指针l第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同l第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表l重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进
39、行，最后得到一个有序序列例初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集
40、：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：算法评价v时间复杂度：l分配：T(n)=O(n)l收集：T(n)=O(RADIX)T(n)=O(d*(n+RADIX)其中：n记录数d关键字位数RADIX基v空间复杂度：S(n)=2*RADIX个队列指针+n个指针域空间v几种内排序方法的比较排序方法 平均时间性能最好时间性能最坏时间性能辅助存储空间稳定性直接
41、插入 O(n2)O(n)O(n2)O(1)稳定希尔O(n1.25)O(1)不稳定冒泡O(n2)O(n)O(n2)O(1)稳定简单选择 O(n2)O(n)O(n2)O(1)不稳定快排O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定堆O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数O(d(n+radix)O(d(n+radix)O(d(n+radix)O(radix)稳定若待排序的记录个数n较小时，可采用直接插入排序或简单选择排序。由于直接插入排序所需记录移动的操作比简单选择排序多，因
42、此当记录本身信息量较大时则采用简单选择排序方法较好。若待排序记录按关键码基本有序，则宜采用直接插入或冒泡排序。当n很大且关键码位数较少时，采用链式基数排序较好。若n较大，则应采用快排、堆或归并排序方法。快排是目前内部排序中被认为最好的方法，当待排序记录的关键码位随机分布时，快排的平均运行时间最短；堆排序的优点是只需一个辅助存储空间，并且不会出现快排可能出现的最坏情况。这两种排序方法都是不稳定排序方法，若要求排序稳定则可选择归并排序。归并排序通常和直接插入排序结合起来使用。9.7 外排序v外排序步骤：用内排序方法将文件一部分一部分进行排序，在外存上生成若干排好序的记录，每一段排好序的记录称为归并
43、段或顺段。对归并段进行反复归并，直到得到有序文件为止。v利用败者树进行多路平衡归并：败者树：记下刚进行完的这场比赛的败者，而让胜者去参加更高一层的比赛。例：5-路归并的败者树的调整6152512374810151691816202240b3b4b0 b1b24612100920213ls0ls1ls2ls3ls46152512374810151691816202240b3b4b0 b1b24612100920213ls0ls1ls2ls3ls4153401152512374810151691816202240b3b4b0 b1b231512104920201ls0ls1ls2ls3ls4152
44、512374810151691816202240b3b4b0 b1b231512104920201ls0ls1ls2ls3ls41810败者树初始化：非终端结点指向含最小关键码的叶子结点，然后从各个叶子结点出发调整非终端结点。b3b4b0 b1b25612105920555ls0ls1ls2ls3ls4例：令b5=MINKEY;b3b4b0 b1b25612105920555ls0ls1ls2ls3ls44b3b4b0 b1b24612105920555ls0ls1ls2ls3ls43b3b4b0 b1b24612103920555ls0ls1ls2ls3ls42b3b4b0 b1b24612103920255ls0ls1ls2ls3ls41b3b4b0 b1b24612103920215ls0ls1ls2ls3ls403