




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、9.1 概述,19.2 插入类排序,9.3 交换类排序,9.4 选择类排序,9.5 归并排序,9.6 分配类排序,9.7 各种排序方法的综合比较,9.8 外部排序,9.1 概 述,一、排序的定义,二、内部排序和外部排序,三、内部排序方法的分类,一、什么是排序?,排序是将一组“无序”的记录序列调整为“有序”的记录序列。,例如:将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,排序的定义: 假设含n个记录的序列为 R1, R2, , Rn 其相应的关键字序列为 K1,
2、 K2, ,Kn ,这些关键字相互之间可以进行比较,即在 它们之间存在着这样一个关系 : Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ,Rpn 的操作称作排序。,二、内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。,反之, 若参加排序的记录数量很大, 整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。,三、内部排序的方法,内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,基于不同的“扩大” 有序序列长度的方法,内部排序方法
3、大致可分下列几种类型:,插入类,交换类,选择类,归并类,其它方法,排序方法还可分为稳定的和不稳定的。,待排记录的数据类型定义如下:,#define n 1000 /待排顺序表最大长度,typedef int KeyType; /关键字类型 typedef struct KeyType key; /关键字项 OtherType other_data;/其它数据项 RecordType; /记录类型 RecordType Ln;,1. 插入类,将无序子序列中的一个个记录“插入”到有序序列中,从而增加记录的有序子序列的长度。,2. 交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记
4、录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。,3. 选择类,从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。,4. 归并类,通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度。,5. 其它方法,9. 2 插 入 排 序,将无序子序列中的记录一个个 “插入”到有序序列中应处的位置,逐渐增加有序子序列的长度。,有序序列r1.i-1,ri,无序序列 ri.n,一趟直接插入排序的基本思想:,有序序列r1.i,无序序列 ri+1.n,找位置,插入,实现“一趟插入排序”可分三步进行:,3将ri 插入
5、(复制)到rj+1的位置上。,2将rj+1.i-1中的所有记录均后移 一个位置;,1在r1.i-1中查找ri的插入位置, r1.j.key ri.key rj+1.i-1.key;,直接插入排序(基于顺序查找),表插入排序(基于链表存储),不同的具体实现方法导致不同的算法描述,折半插入排序(基于折半查找),希尔排序(基于逐趟缩小增量),一、直接插入排序,利用 “顺序查找”实现 “在r1ri-1中查找ri的插入位置”,算法的实现要点:,1. 从ri-1起向前进行顺序查找, 监视哨设置在r0;,循环结束确定ri的插入位置为 j +1,r0,j,ri,j=i-1,插入位置,2. 将所有 j+1 到
6、i 的记录向后移动 1 个 位置, 然后可以直接进行“插入”。,3. 可以在查找的同时实现记录向后移动;,r0=ri; j=i-1; k=r0.key; while(krj.key) rj+1= rj; j-; ,r0,j,ri,j= i-1,4. 上述循环结束后可以直接进行“插入”,插入位置,令 i = 2,3, n,实现整个序列排序。,void InsSort(RecordType r,int length) /对记录数组r做直接插入排序,length为数组的长度 for(i=2;i0 /插入q和p之间 ,四、希尔排序(又称缩小增量排序),基本思想:对待排记录序列先作“宏观”调整,再作“微
7、观”调整。,所谓“宏观”调整,指的是,“跳跃式” 的插入排序。 具体做法为:,将记录序列分成若干子序列,分别对每个子序列进行插入排序。,其中, d 称为增量, 它的值在排序过程中从大到小逐渐缩小, 直至最后一趟排序减为 1 .,例如:将 n 个记录分成 d 个子序列: r1,r1+d,r1+2d, , r1+kd r2,r2+d,r2+2d, , r2+kd rd, r2d, r3d, , r(k+1)d ,例如:,16 25 12 30 47 11 23 36 9 18 31,第一趟希尔排序,设增量 d =5,11 23 12 9 18 16 25 36 30 47 31,第二趟希尔排序,设
8、增量 d = 3,9 18 12 11 23 16 25 31 30 47 36,第三趟希尔排序,设增量 d = 1,9 11 12 16 18 23 25 30 31 36 47,9.3 交换类排 序,一、起泡排序,二、一趟快速排序,三、快速排序,四、快速排序的时间分析,一、起泡排序,假设在排序过程中,记录序列r1.n的状态为:,第 i 趟起泡排序,无序r1rn-i+1,有序 rn-i+2rn,n-i+1,无序r1rn-i,有序 rn-i+1rn,比较相邻记录,将关键字最大的记录交换到 n-i+1 的位置上,proc bsort(r:array1.n; n integer); i:= n;
9、while i 1 do for j:=1 to i do if (rj+1.key 1 do laste=1; for(j=1;j=i;j+) if (rj+1.key rj.key) swap(rj, rj+1); laste= j; /记下进行交换的记录位置 ; i= laste; /本趟最后一次进行交换的记录位置 ,注意:,2. 一般情况下,每经过一趟“起泡”, “i减1”,但并不是每趟都如此。,例如:,2,5,5,3,1,5,7,9,8,9,i=7,i=6,for(j=1;j=i;j+) if (rj+1.key rj.key) ,1,3,i=2,1. 起泡排序的结束条件为, 最后一
10、趟没有进行“交换记录”。,laste,laste,1,1,3,2,时间分析:,最好的情况(关键字在记录序列中顺序有序): 只需进行一趟起泡,“比较”的次数:,最坏的情况(关键字在记录序列中逆序有序): 需进行n-1趟起泡,“比较”的次数:,0,“移动”的次数:,“移动”的次数:,n-1,起泡排序一趟之后,使最大的记录定位到最后,如果一趟之后可使某记录定位在它在有序序列应处的位置,而将其余的无序序列以它为枢轴,分成两部分,比它小的放在它的前面,比它大的的放在它的后面,下一趟分别对前后的子序列排序,显然可加快速度。这就是快速排序。,二、快速排序,一趟快速排序(一次划分),目标:找一个记录,以它的关
11、键字作为“枢轴”,凡其关键字小于枢轴的记录均移动至该记录之前,反之,凡关键字大于枢轴的记录均移动至该记录之后。,致使一趟排序之后,记录的无序序列rs.t将分割成两部分:rs.i-1和ri+1.t,且 rj.key ri.key rj.key (sji-1) 枢轴 (i+1jt)。,s,t,low,high,设 rs=52 为枢轴,将 rhigh.key 和枢轴的关键字进行比较,要求 rhigh.key 枢轴的关键字,将 rlow.key 和 枢轴的关键字进行比较,要求 rlow.key 枢轴的关键字,high,23,low,80,high,14,low,52,例如,rs,52,可见,经过“一次
12、划分” ,将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75,在调整过程中,设立了两个指针: low 和high,它们的初值分别为: s 和 t,,之后逐渐减小 high,增加 low,并保证 rhigh.key52,和 rlow.key52,否则进行记录的“交换”(实际只需赋值)。,int qpass(RecordType r,int s,int t); /本算法对rsrt进行一趟快速排序 i=s; j=t; p=ri; x=p.key; /选p为枢轴 while
13、(i=x)j-; ri=rj; /从右向左找到rj.keyx ri=p; /枢轴归位 return i; /返回枢轴位置 ,三、快速排序,首先对无序的记录序列进行“一次划分”,之后分别对分割所得两个子序列“递归”进行快速排序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,void qsort(RecordType r,int s,int t) /对记录序列rsrt进行快速排序 if( s=2;i-) h=r1; /将堆顶记录和最后记录互换 r1=ri; ri=h; sift(r,1,i-1); /对 r1筛选,使r1.i-1重新变为堆
14、,堆排序的时间复杂度分析:,1. 对深度为 k 的堆,“筛选”所需进行的关键字 比较的次数至多为2(k-1);,3. 调整“堆顶” n-1 次,总共进行的关键 字比较的次数不超过 2( log2(n-1)+log2(n-2)+log22)2n(log2n),因此,堆排序的时间复杂度为O(nlogn)。,2. 对 n 个关键字, 建成深度为h(=log2n+1)的堆, 所需进行的关键字比较的次数至多 4n;,9.5 归 并 排 序,归并排序的过程基于下列基本思想进行: 将两个或两个以上的有序子序列 “归并” 为一个有序序列。,在内部排序中,通常采用的是2-路归并排序。即:将两个位置相邻的记录有序
15、子序列,归并为一个记录的有序序列。,有 序 序 列 rs.t,有序子序列 rs.m,有序子序列 rm+1.t,这个操作对顺序表而言,是轻而易举的。,void Merge( RT r1,int s,int m,int t,RT r) /*已知r1s.m和r1m+1.t分别按关键字有序排列,将它们合并成一个有序序列rs.t */ i=s;j=m+1; k=s; while( i=m if( s=t ) rf=r1f; else m=(s+t)/2; MSort(r1,s,m,r2); MSort(r1,m+1,t, r2); Merge(r2,s,m,t,r); free(r2); /* Merg
16、eSort */,例如:,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80 36, 68, 14, 52, 2380, 52, 23, 52, 23, 52, 80,36, 6814,3668,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,每一趟归并的时间复杂度为 O(n), 总共需进行 log2n 趟。 所以,对 n 个记录进行归并排序的时间复杂度为(nlogn)。 归并排序所需的辅助存储空间为: O(n),9.6 分配类排序,分配类排序则利用分配和收集两种基本操作,基数类排序就是典型的分配类排序。,9.
17、6.1 多关键字排序,如:将扑克牌的排序过程看成花色和面值两个关键字的排序问题。若规定花色和面值的顺序如下: 花色:梅花 方块 红桃 黑桃 面值:A2310JQK 并进一步规定花色的优先级高于面值,则一副扑克牌从小到大的顺序为:梅花A,梅花2,梅花K;方块A,方块2,方块K;红桃A,红桃2,红桃K;黑桃A,黑桃2,黑桃K。,有两种方法,一种是:先按花色分成有序的四类,再按面值对每类从小到大排序; 称为“高位优先”排序法。另一种方法是分配与收集交替进行;先按面值从小到大把牌分配成13叠(每叠4张),然后按面值的次序将各叠牌收集为一叠,再将牌按花色摆成4叠,每叠有13张牌,最后按花色的次序把这4叠
18、牌收集到一起,就得到有序序列。此法称为“低位优先”排序法。,又如:学生记录含三个关键字: 系别、班号和班内的序列号,其中以系别为最主位关键字。,无序序列,对K2排序,对K1排序,对K0排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序过程如下:,二、链式基数排序,假如多关键字的记录序列中,每个关键字的取值范围相同,则按LSD法进行排序时,可以采用“分
19、配-收集”的方法,其好处是不需要进行关键字间的比较。,对于数字型或字符型的单关键字,可以看成是由多个数位或多个字符构成的多关键字,此时可以采用这种“分配-收集”的办法进行排序,称作基数排序法。,例如:对下列这组关键字 209, 386, 768, 185, 247, 606, 230, 834, 539,首先按其 “个位数” 取值分别为 0, 1, , 9 “分配” 成 10 组,之后按从 0 至 9 的顺序将 它们 “收集” 在一起;,然后按其 “十位数” 取值分别为 0, 1, , 9 “分配” 成 10 组,之后再按从 0 至 9 的顺序将它们 “收集” 在一起;,最后按其“百位数”重复
20、一遍上述操作。,在计算机上实现基数排序时,为减少所需辅助存储空间,应采用链表作存储结构,即链式基数排序,具体作法为:,待排序记录以指针相链,构成一个链表;,“分配” 时,按当前“关键字位”所取值,将记录分配到不同的 “链队列” 中,每个队列中记录的 “关键字位” 相同;,“收集”时,按当前关键字位取值从小到大将各队列首尾相链成一个链表;,对每个关键字位均重复 2) 和 3) 两步。,例如:,p369367167239237138230139,进行第一次分配,进行第一次收集,f0 r0,f7 r7,f8 r8,f9 r9,p230,230,367 ,167,237,367167237,138,3
21、69239139,369 ,239,139,138,进行第二次分配,p230237138239139,p230367167237138369239139,f3 r3,f6 r6,230 ,237,138,239,139,367 ,167,369,367167369,进行第二次收集,进行第三次收集后便得到记录的有序序列,f1 r1,p230237138239139367167369,进行第三次分配,f2 r2,f3 r3,138 ,139,167,230 ,237,239,367 ,369,p138139167,230237239,367369,提醒注意:,“分配”和“收集”的实际操作仅为修改链
22、表中的指针和设置队列的头、尾指针; 可使用静态链表。,基数排序的时间复杂度为O(d(n+rd),其中:分配为O(n) 收集为O(rd)(rd为“基”) d为“分配-收集”的趟数,9.7 各种排序方法的综合比较,一、时间性能,1. 平均的时间性能,基数排序,时间复杂度为 O(nlogn):,快速排序、堆排序和归并排序,时间复杂度为 O(n2):,直接插入排序、起泡排序和 简单选择排序,时间复杂度为 O(n):,希尔排序dk=2t-k+1-1 时为O(n3/2),2. 当待排记录序列按关键字顺序有序时,3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,直接插入排序和
23、起泡排序能达到O(n)的时间复杂度,直接插入排序最佳 快速排序的时间性能蜕化为O(n2) 。,二、空间性能,排序过程中所需的辅助空间大小,1. 所有的简单排序方法(包括:直接插入、 起泡和简单选择) 和堆排序的空间复杂度为O(1);,2. 快速排序为O(logn),为递归程序执行过程中,栈所需的辅助空间;,3. 归并排序所需辅助空间最多,其空间复杂度为 O(n);,4. 链式基数排序需附设队列首尾指针,则空间复杂度为 O(rd)。,三、排序方法的稳定性能,1. 稳定的排序方法指的是, 对于两个关键字相等的记录, 它们在序列中的相对位置, 在排序之前和经过排序之后, 没有改变。,2. 当对多关键
24、字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。,排序之前 : Ri(K) Rj(K) ,排序之后 : Ri(K) Rj(K) ,例如:,排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ),若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的;,若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。,3. 对于不稳定的排序方法,只要能举出一个实例说明即可。,4. 快速排序、堆排序和希尔排序是不稳定的排序方法。,例如 : 对 4, 3, 4,
25、2 进行快速排序, 得到 2, 3, 4, 4 ,四、关于“排序方法的时间复杂度的下限”,本章讨论的各种排序方法,除基数排序外,其它方法都是基于“比较关键字”进行排序的排序方法。,可以证明, 这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于 “比较关键字”的排序方法,所以它不受这个限制。),例如:对三个关键字进行排序的判定树如下:,K1K3,K1K2,K1K3,K2K3,K2 K3,K2K1K3,K1K2K3,K3K2K1,K2K3K1,K3K1K2,K1K3K2,树上的每一次“比较”都是必要的;,树上的叶子结点包含所有可能情况。,n,y,一般情况下, 对n个关键字进
26、行排序, 可能得到的结果有n! 种, 由于含n! 个叶子结点的二叉树的深度 hlog2(n!) +1, 则对 n 个关键字进行排序的比较次数至少是 h- log2(n!) nlog2n (斯蒂林近似公式)。,所以, 基于“比较关键字”进行排序的 排序方法, 可能达到的最快的时间复杂度为 O(nlogn)。,一. 问题的提出,待排序的记录数量很大,不能一次装入内存,则无法利用前几节讨论的排序方法(否则将引起频繁访问外存);,9.8 外 部 排 序,. 对外存中数据的读/写是以“数据块” 为单位进行的; 读/写外存中一个“数据块”的数据所需要的时间为: TI/O = tseek + tla + n
27、 twm 其中 tseek 为寻查时间(查找该数据块所在磁道) tla 为等待(延迟)时间 n twm 为传输数据块中n个记录的时间。,按可用内存工作区的大小,利用内部排序方法,构造若干( 记录的) 有序子序列,通常称外存中这些记录有序子序列为 “归并段”;,二、外部排序的基本过程,由相对独立的两个步骤组成:,通过“归并”, 逐步扩大 (记录的)有序子序列的长度, 直至外存中整个记录序列按关键字有序为止。,例如:假设有一个含10000个记录的磁盘文件,而所用的计算机内存工作区一次只能对1000个记录进行内部排序,则首先利用内部排序的方法得到10个初始归并段,然后进行逐趟归并。,假设进行2路归并
28、(即两两归并),则 第一趟由10个归并段得到5个归并段;,最后一趟归并得到整个记录的有序序列。,第三趟由 3 个归并段得到2个归并段;,第二趟由 5 个归并段得到3个归并段;,R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R2 R14,假设“数据块”的大小为200,即每次访问外存可以读/写200个记录。 则对于10,000个记录,处理一遍需访问外存100次(读和写各50次)。,分析外部排序访问外存(对外存读/写)的次数:,对上述例子而言: 1) 求得10个初始归并段需访问外存100次; 2) 每进行一趟归并需访问外存100次
29、; 3) 总计访问外存 100 + 4100 = 500次。 (100+480+220=460),R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R6 R7 R8 R1 R2 R3 R4 R1 R2 R14,第一趟由10个归并段得到8个归并段;,总计访问外存: 100+360+440=440 次,外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间,显然, 除去内部排序的因素外, 外部排序的时间取决于逐趟归并所需进行的“趟数”。,例如: 上例采用4路归并,则只需进行 2 趟归并,访问外存总次数压缩到 100 + 2 100 = 300 次。,对n个记录的文件进行外排序, 假设待排记录序列含m 个初始归并段, 采用k路归并, 则归并趟数为 s = logkm , 显然随着 k 的增大, 归并的趟数将减少, 因此对外排而言, 通常采用多路归并。k 的大小可选, 但需综合考虑各种因素, (2k个输入缓冲和2个输出缓冲, 实现并行操作) k路归并每个记录内部归并比较次数为(k-1),内部归并过程进行的总比较次数为:,k-路归并时比较次数将随k值增加而增加, 抵消一部分增加 k 值而减少外存读写时间带来的效益; 利用失败树 进行树形选择, 可减少 比较次数。
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 矿山智能化监测与数据驱动的治理研究-洞察阐释
- 网络设备配置发现-洞察阐释
- 机械装备可靠性评估-洞察阐释
- 智能化后勤管理系统开发与评估-洞察阐释
- 城乡一体化规划与实践-洞察阐释
- 饲料中离凹凸棒石对肉鸡健康的影响研究
- 算法作品的版权与著作权归属研究
- 虾爪状手的护理课件
- 癫痫患者的护理查房
- 丘脑继发恶性肿瘤护理
- 办公室主任职业规划
- 第九章新时代中国特色大国外交与构建人类命运共同体-2024版研究生新中特教材课件
- 出国工作合同范例
- 《执法规范化建设探究的国内外文献综述》2700字
- 大学物业服务月考核评价评分表
- 19G522-1钢筋桁架混凝土楼板图集
- GB/T 19963.2-2024风电场接入电力系统技术规定第2部分:海上风电
- 2024年广西南宁市市场监督管理局招聘外聘人员3人历年高频500题难、易错点模拟试题附带答案详解
- 2024年黑龙江大兴安岭中考生物试题及答案1
- 2024详解国家基层糖尿病防治管理指南
- 云南省2023年秋季学期期末普通高中学业水平考试信息技术(含答案解析)
评论
0/150
提交评论