1、19.1 基本概念n目的：n实现快速查找n定义：n调整原文件中的记录顺序，使之按关键字递增(或递减)次序排列起来。n其形式化定义描述如下：n输入：n个记录r1，r2，rn，其相应的关键字分别为k1，k2，knn输出：rl，r2，rn，使得k1k2kn。n (或k1k2kn)/有序升序或者降序9.1 基本概念n默认的排序数据结构：#define MAXSIZE 100 typedef int KeyType；/*假定关键字类型为整数类型*/typedef struct KeyType key；/*关键字项*/OtherType other；/*其他项*/DataType；/*数据元素类型*/ty
2、pedef struct DataType rMAXSIZE+1；/*r0闲置或充当前哨站*/int length；/*顺序表长度 */SqList；/*顺序表类型*/9.1 基本概念n分类n内排序n外排序n稳定性n稳定排序n不稳定排序n基本操作n比较两个关键字大小n将记录从一个位置移动到另一个位置9.2 插入排序n基本思想n通过构建有序序列，将待排序的数据，在已排好序的序列中从后向前扫描，找到其相应位置并进行插入操作。n常见的插入排序算法n直接插入排序n折半插入排序n希尔排序 9.2.1 直接插入排序void StraightInsertSort(SqList*S)int i，j；for(i
3、=2；ilength；i+)S-r0=S-ri；/*复制为哨兵*/j=i-1;while(S-r0.key rj.key)S-rj+1=S-rj；j-;/*记录后移*/S-rj+1=S-r0；/*插入到正确位置插入到正确位置*/2/89.2.1 直接插入排序n空间效率：O(1)n一个辅助单元r0n时间效率：n最好情况：O(n)n最坏情况:O(n2)n总的比较次数=次n总的移动次数=次n一般情况:O(n2)211(1)2nini2)1(211nini2211(1)*(2)2224niinnnn9.2.3 希尔排序举例举例:8194119612351795285841751596281258813
4、541941775119515步长步长=596419411285835759512811715步长步长=3步长步长=1964194112858357595128117159.2.3 希尔排序n希尔排序算法描述：n（1）选择一个步长序列t1，t2，ti，tk，其中titi+1，tk=1；n（2）按步长序列个数k，对序列进行k趟排序；n（3）每趟排序，根据对应的步长ti，将待排序列分割成若干个子序列，分别对各子序列进行直接插入排序。仅当步长为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。9.2.3 希尔排序nShell排序算法描述如下：void ShellInsert(SqList*s
5、，int gap)/*一趟增量为gap的插入排序，gap为步长*/int i,j；for(i=gap+1；ilength；i+)if(S-ri.keyri-gap.key)/*小于时，需将ri插入有序表*/S-r0=S-ri；/*为统一算法设置监视哨*/for(j=i-gap；j0&S-r0.keyrj.key；j=j-gap)S-rj+gap=S-rj；/*记录后移*/S-rj+gap=S-r0；/*插入到正确位置*/*if*/9.2.3 希尔排序nShell排序算法描述如下：void ShellSort(SqList*s，int gaps，int t)/*按增量序列gaps0，1，t-1对
6、顺序表S作希尔排序*/int k；for(k=0；kr2.key，则将两个记录交换，紧接着依次比较r2和r3，直至rn-1与rn为止。这样一趟将关键字值最大的记录移至rn位置，n第二趟：比较r1至让rn-1，关键字值次大的记录移动到第n-1位置，方法同第一趟n依次完成第3趟，第4趟，n-1趟，直到所有记录都完成排序9.3.1 冒泡排序n举例758768928861779680727587689288617796807268879288619277929296809672968768758761778880729296687561778780728892966861757780728788929
7、66168757772808788929661687572778087889296616872757780878892966168727577808788929661687275778087889296616872757780878892969.3.1 冒泡排序n算法描述：void BubbleSort(SqList*s)/*对顺序表S作冒泡排序*/int i,j;for(i=1；ilength-1；i+)/*进行n-1趟排序*/for(j=2;jlength-i;j+)if(S-rj.key rj-1.key)S-r0=S-rj；/*S-rj与S-rj-1交换 */S-rj=S-rj-1;S
8、-rj-1=S-r0;n-1次ni次比较9.3.1 冒泡排序n算法空间复杂度为O(1)n总的比较次数为：n总的交换次数最多为O(n2)，最少为0 n平均交换次数为:n n起泡排序是稳定的：S-rj.key rj-1.key交换)(2/)1()(211maxnOnninCni)(4/)1(2/)(211maxnOnninMni改进的起泡排序改进的起泡排序9.3.1 冒泡排序n改进后的冒泡排序算法void BubbleSort(SqList*s)/*对顺序表S作冒泡排序*/int i,j;int flag=0；for(i=1;!flag&ilength-1;i+,flag=0)/*进行n-1趟排序
9、*/for(j=2;jlength-i;j+)if(S-rj.key rj-1.key)flag=1;S-r0=S-rj；/*S-rj与S-rj-1交换 */S-rj=S-rj-1;S-rj-1=S-r0;9.3.2 快速排序n算法思想：n将一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，然后分别对这两部分记录继续使用该方法排序，以达到整个序列有序。13 8192 43 6531 57 2675 013 43 31 57 26 0658192 750 13 26 31 43 576575 81 920 13 26 31 43 57 65 75 81 92
10、9.3.2 快速排序n具体步骤：1.待排序序列S中任意选择一个记录r作为轴值（设记录r的关键字为k)；2.将剩余的记录分割成两个子序列L和R,子序列L中的关键字均小于或等于k，子序列R中所含记录的关键字均大于或等于k；3.将子序列L中所有记录放在记录r左边，子序列R中所有记录放在记录r右边；4.对于子序列L和R递归进行快速排序，直到子序列中只含有0或1个元素，退出递归。9.3.2 快速排序n举例：491438749665849552749lowhigh27lowlowlow74highhigh=high96highhigh4912345678910027143884965964955749.3
11、.2 快速排序n一趟快速排序的算法描述int QuickSort1(SqList*s,int low,int high)KeyType pivotkey;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;/*轴值
12、（支点）记录到位*/return low;/*返回轴值（支点）记录所在位置*/9.3.2 快速排序n快速排序的递归算法描述void QuickSort(SqList*s,int low,int high)/*对顺序表S中的子序列rlowhigh作快速排序*/int pivotloc;if(lowhigh)pivotloc=QuickSort1(S,low,high);/*将待排序序列一分为二*/QuickSort(S,low,pivotloc-1);/*对小于轴值序列实现递归排序*/QuickSort(S,pivotloc+1,high);/*对大于轴值序列实现递归排序9.3.2 快速排序n算
13、法分析n最坏情况：n每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数如下：112)(2/)1()(ninOnnin比较次数的最大值9.3.2 快速排序n最好情况：最好情况：n每次所取的pivotkey是当前无序区的“中值”，划分的结果是pivotkey的左右两个无序子区的长度大致相等n设C(n)表示长度为n的序列快速排序的比较次数，它等于长度为n的无序区进行比较次数n-1，加上对划分所得的左右两个无序子区进行快速排序所需的比较次数，假设文件长
14、度n=2k，k=log2n，有：n)O(nlognC(1)nnlog)C(n/22kn.)8C(n/23n)2C(n/24n/42n)4C(n/22n)2C(n/22n/2n2C(n/2)nC(n)22kk33229.4 选择排序n基本思想：n一趟从待排序列中选取一个关键字最小的记录，即第一趟从n个记录中选取关键字最小的记录，第二趟从剩下的n-1个记录中选取关键字次小的记录，直到整个序列的记录选完为止。这样根据选取记录的顺序，可得到按关键字有序的序列 n常见选择排序算法n简单选择排序n堆排序9.4.1 简单选择排序n算法步骤n第1趟，从n个待排序记录中找出关键字最小的记录与第一个记录交换；n
15、第2趟，从第二个记录开始的n-1个待排序记录中再选出关键字最小的记录与第二个记录交换；n 第i趟，则从第i个记录开始的n-i+1个待排序记录中选出关键字最小的记录与第i个记录交换，直到整个序列有序。9.4.1 简单选择排序n举例75876892886177968072t758768928861779680726175第第趟趟1 2t6887i123456789103t72874t75925t77886t80927t87888t88969t109.4.1 简单选择排序n算法描述void SelectSort(SqList*s)for(i=1；ilength；i+)/*作S-length-1趟选取
16、*/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条记录交换*/9.4.1 简单选择排序n算法分析：n简单选择排序第i趟排序中选出关键字最小的记录，需做n-i次比较，因此总的比较次数为：n辅助空间为O(1)，简单选择排序是不稳定的。简单选择排序是不稳定的。)(2/)1()(211nOnninni9.4.2 堆排序n人物介绍n威廉姆斯（JWilliams）n罗
17、伯特弗洛伊德（1936.6.8-2001.9.25）n自学成才的计算机科学家(美国纽约)n1978年图灵奖得主n1953年获得文学士学位n1958年获得理科学士学位 n1965年被卡内基梅隆大学聘为副教授n1970年被斯坦福大学聘为教授 n算法，程序设计语言的逻辑和语义，自动程序综合，自动程序验证，编译器的理论和实现等方面都作出创造性的贡献。9.4.2 堆排序n算法方面n1964年发明了著名的堆排序算法(和J.Williams)n以弗洛伊德命名的求最短路的算法 n程序设计方面n前后断言法的创始人 nFloyd-Evans Production Language(R0Evans)n1962年，完
18、成了Algol 60编译器的开发 9.4.2 堆排序n堆定义nn个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：(1)kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i)。n若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。9.4.2 堆排序n堆示意图36 24 85 47 53 30 12 98 47 85 24 36 30 53 98 16 大根堆小根堆9.4.2 堆排序n基本思路：n对一组待排序的键值，首先是把它
19、们按堆的定义排列成一个序列（称为初键堆），这就找到了最小键值。然后将最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进行，直到把全部键值排好序为止。n堆排序的基本操作：n（1）调整子树为堆；n（2）排序。9.4.2 堆排序n举例（建堆）47 241285 36913053533630914712248501234567918530123012859112531253245324539.4.2 堆排序n第n个元素进行筛选的算法描述：void HeapAdjust(SqList*s，int n，int m)int i,j;DataType rc;rc=S-rn；i=n;for(j=2
20、*i；j=m；j=j*2)/*沿关键字较大的孩子结点向下筛选*/if(jrj.keyrj+1.key)j=j+1；/*为关键字较大的元素下标*/if(rc.keyS-rj.key)break；/*rc应插入在位置i上*/S-ri=S-rj；i=j；/*使i结点满足堆定义*/S-ri=rc；/*插入*/9.4.2 堆排序n堆排序算法描述：void HeapSort(SqList*s)int i;for(i=S-length/2；i0；i-)/*将r1.length建成堆*/HeapAdjust(S，i，S-length)；for(i=S-length；i1；i-)S-r1S-ri；/*堆顶与堆底
21、元素交换,将最大元素移到后面*/HeapAdjust(S，1，i-1)/*将r1.i-1重新调整为堆*/9.4.2 堆排序n算法分析：n堆排序适合记录很多的情形，它的时间复杂度为O(nlog2n)。堆排序中初始建堆虽然时间复杂度为O(n)，但每次调整后面的花费时间很少。n堆排序算法中增加了一个辅助空间，辅助空间为O(1)。n堆排序时间效率基本与待排序记录的初始状态无关n堆排序是不稳定的堆排序是不稳定的9.5 归并排序n分治法n快速排序n快速排序将待排序序列分割成两个子序列，然后分别递归调用对两个子序列进行快速排序，它侧重于分割过程。n归并排序n归并排序是将原始序列分成两个子序列，然后分别对每个
22、子序列执行递归调用，最后再将已排好序的子序列合并，侧重于归并过程。9.5 归并排序n归并排序思路：n归并的含义是将两个或两个以上的有序表合并成一个有序表。利用归并的思想就可以实现排序。假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。135790246801234567899.5 归并排序n举例7587689261887796728068758792617788967280616875778788929672806168727577
23、808788929675876892886177968072归归并并过过程程9.5 归并排序n一趟归并算法：void Merge(DataType r，DataType rf，int u，int v，int t)/*将有序的ruv和rv+1t归并为有序的rfut*/int i,j,k;for(i=u，j=v+1，k=u；i=v&j=t；k+)/*将r中记录由小到大并到tf */if(ri.key=rj.key)rfk=ri；i+；elserfk=rj；j+；while(i=v)rfk+=ri+；/*将剩余的riv复制到rf*/while(jr，S-r，1，S-length)；9.5 归并排序n
24、算法分析n对n个元素的归并排序，两两过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n次，故时间复杂度为O(nlog2n)。n 归并排序在最好和最坏情况下的时间复杂度都为O(nlog2n)。n 归并排序是稳定的排序 9.6 基数排序设n个元素的排序表中的每个记录包含d个关键码k1，k2，kd)，称序列对关键码k1,k2，kd)有序是指：对于序列中任两个记录Ri和Rj(1ijn)都满足下列有序关系：(ki1，ki2，ki3，kid)(kj1，kj2，kj3，kjd)其中kl称为最主位关键码，kd称为最次位关键码9.6 基数排序n多关键码排
25、序按照从最主位关键码到最次位关键码，或从最次位关键码到最主位关键码的顺序逐次排序，分两种方法：(1)最主位优先(Most Significant Digit First)法，简称MSD法，即先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子表排序后。再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法1即是MSD法。(2)最次位优先(Least Significant Digit First)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对kl排序后便得到
26、一个有序序列。扑克牌按花色、面值排序中介绍的方法2即是LSD法。9.6 LSD链式基数排序n从最低位关键码起，按关键码的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”，称之为一趟排序，第一趟之后，排序表中的记录已按最低位关键码有序，再对次最低位关键码进行一趟“分配”和“收集”，如此，直到对最高位关键码进行一稍“分配”和“收集”，则排序表按关键字有序。n以用链表作为排序表的存储结构，用RADIX个链队列作为分配队列，关键码相同的记录存入同一个链队列中，收集则是将各链队列按关键码大小顺序链接起来。9.6 LSD链式基数排序例：以静态链表存储的排序表的基数排序过程如下系列图所示。排
27、序表记录关键字为：179，208，306，93，859，984，55，9，271，33。9.6 LSD链式基数排序 9.6 LSD链式基数排序 9.6 LSD链式基数排序算法#define KEY_NUN 8 *关键码项数 */#define RADIX 10 *关键码基数，此时为十进制整数的基数*/#define MAX_SPACE 1000 *分配的最大可利用存储空间*/typedef struct KeyType keysKEY NUM;*关键码宇段*/InfoType otheritems;*其他字段*/int next;*指针字段*/NodeType;*静态链表结点类型*/typed
28、ef struct int f;int e;Q_Node;typedef Q_Node QueueRADIX;*各队列的头尾指针*/9.6 LSD链式基数排序算法 void Distribute(NodeType R,int i,Queue q)/*分配算法：静态链表R中的记录已按Key0,Key1,Keyi-1有序按照第i个关键码Keyi建立RADIX子表，使同一个子表中的记录的Keyi相同，qi.f 和qi.e0分别指向第i个子表的第一个和最后一个记录。*/int j,p;for(j=0;jRADIX;j+)qj.f=qj.e=0;/*各子表初始化为空*/for(p=R0.next;p;p
29、=Rp.next)j=ord(Rp.keysi);/*ord将记录中第i各关键码映射到0RADIX-1中*/if(!qj.f)qj.f=qj.e=p;/*第一个元素插入队列qj*/else Rqj.e.next=p;qj.e=p;/*将p所指的节点插入到第j个队列中*/9.6 LSD链式基数排序算法 void Collect(NodeType R,int i,Queue q)/*收集算法，按照q0qRADIX-1所指各子表依次链接成一个链表*/int t,j;for(j=0;!qj.f;j=succ(j);/*找到第一个非空子表，succ为求后继函数*/R0.next=qj.f;t=qj.e;
30、while(jRADIX)for(j=succ(j);jRADIX&!qj.f;j=succ(j);/*找到下一个非空子表*/if(qj.f)Rt.next=qj.f;t=qj.e;/*链接两个非空子表*/Rt.next=0;/*t指向最后一个非空子表中的最后一个节点*/9.6 LSD链式基数排序算法 void RadixSort(NodeType R,int n)/*对R作基数排序，使其成为按照关键字升序的静态链表，R0是头节点*/int i;Queue q;for(i=0;in;i+)Ri.next=i+1;Rn.next=0;/*初始化，定义静态链表*/for(i=0;iKEY_NUM;
31、i+)Distribute(R,i,q);/*第i趟分配和第i趟收集*/Collect(R,i,q);9.6 LSD链式基数排序性能分析 从时间复杂度看，设待排序列为n个记录，d位关键码，每位关键码的取值范围为0REDIX-1，则进行链式基数排序的时间复杂度为O(d(n+REDIX)，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(REDIX)，共进行d趟分配和收集。从空间复杂度看，需要2*RADIX个队列头尾指针辅助空间，以及用于静态链表的n个指针。本章小结算法算法最大时间最大时间平均时间平均时间最小时间最小时间辅助空辅助空间代价间代价稳定性稳定性直接插入排序直接插入排序O(n2
32、)O(n2)O(n)O(1)稳定稳定折半插入排序折半插入排序O(n2)O(n2)O(nlog2n)O(1)稳定稳定*Shell排序排序O(n2)O(n3/2)O(1)不稳定不稳定*冒泡排序冒泡排序O(n2)O(n2)O(n2)O(1)稳定稳定快速排序快速排序O(n2)O(nlog2n)O(nlog2n)O(logn)不稳定不稳定简单选择排序简单选择排序O(n2)O(n2)O(n2)O(1)不稳定不稳定堆排序堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定不稳定2-路归并排序路归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定基数排序基数排序O(d(n+REDIX)O(d(n+REDIX)O(rd)稳定稳定
