资源预览内容
第1页 / 共47页
第2页 / 共47页
第3页 / 共47页
第4页 / 共47页
第5页 / 共47页
第6页 / 共47页
第7页 / 共47页
第8页 / 共47页
第9页 / 共47页
第10页 / 共47页
亲,该文档总共47页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构计算机与信息学院 刘勇每课一贴: 古之立大事者,不惟有超世之才,亦必有 坚忍不拔之志。 苏轼有志者,事竟成,破釜沉舟,百二雄关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。 蒲松龄1数据结构计算机与信息学院 刘勇3.选择排序简单选择排序:矮子里面挑将军,或反之 v排序过程:选择未排序序列中最小者与该序列第一个元素交换v算法评价 l时间复杂度 u记录移动次数 Y最好情况:0 (正序) Y最坏情况:3(n-1) (逆序) u比较次数:l空间复杂度:S(n)=O(1) l稳定性:不稳定,反例2,2,1 T(n)=O(n)上节课内容回顾2数据结构计算机与信息学院 刘勇9.2 交换排序(通过交换的方式实现排序) 1.冒泡排序l 时间复杂度:T(n)=O(n2) l 空间复杂度:S(n)=O(1) l 算法稳定v排序过程l 重复关键字比较与交换,第一趟冒泡排序,结果关键字 最大的记录被安置在最后一个记录上第二趟冒泡排序, 结果使关键字次大的记录被安置在第n-1个记录位置,重 复上述过程,直到“在一趟排序过程中没有进行过交换记 录的操作”为止上节课内容回顾3数据结构计算机与信息学院 刘勇v 算法再改进 1 2 3 6 5 4 上述冒泡排序还可做如下改进:即记住最 后一次交换发生位置lastExchange的冒泡排序.在“自下向上”冒泡排序每趟扫描中,记 住最后一次交换发生的位置lastExchange,(该 位置之前的相邻记录均已有序).下一趟排序开 始时,R1lastExchange-1 是有序区 ,RlastExchangen是无序区。这样一趟排序 可能使当前有序区扩充多个记录,从而减少排 序的趟数,有奖征集该程序。 4数据结构计算机与信息学院 刘勇冒泡排序改进算法: void BubbleSort(SeqList R) int i,j,lastexchage;Boolean exchange; /交换标志for(i=1;i=i;j-) /对当前无序区Rin自下向上扫描if(Rj+1.key=lastexchange; j-) /对当前无序区Rin自下向上扫描if(Rj+1.keyRj.key)/交换记录R0=Rj+1; /R0不是哨兵,仅做暂存单元Rj+1=Rj;Rj=R0;lastexchange=j; /BubbleSort有问题的改进算法:6数据结构计算机与信息学院 刘勇v基本思想:通过一趟排序,将待排序记录分割成独 立的两部分,其中一部分记录的关键字均比另一部 分记录的关键字小,则可分别对这两部分记录进行 排序,以达到整个序列有序 v排序过程:令序列第一个元素关键字为枢轴,将序 列一份为二,递归进行排序。2. 交换排序快速排序:v算法评价 l时间复杂度 u最好情况(每次总是选到中间值作枢轴) T(n)=O(nlog2n) u最坏情况(每次总是选到最小或最大元素作枢轴) T(n)=O(n) l空间复杂度:需栈空间以实现递归 u最坏情况:S(n)=O(n) u一般情况:S(n)=O(log2n) l算法不稳定,反例2,2,1 7数据结构计算机与信息学院 刘勇4. 选择排序堆排序v 堆的定义:n个元素的序列(k1,k2,kn),当且仅当满 足下列关系时,称之为堆或(i=1,2,.n/2)kik2i kik2i+1kik2i kik2i+1小根堆 大根堆 v堆排序:将无序序列建成一个堆,输出堆顶并重构d 堆,重复执行即可得到有序序列,这个过程叫v关键问题解决方法筛选 l 方法:输出堆顶元素之后,以堆中最后一个元素替代之;然 后将根结点值与左、右子树的根结点值进行比较,并与其中小 者进行交换;重复上述操作,直至叶子结点,将得到新的堆,称 这个从堆顶至叶子的调整过程为“筛选”8数据结构计算机与信息学院 刘勇v建堆方法 l方法:从无序序列的第n/2 个元素(即此无序序列对应的完全 二叉树的最后一个非终端结点)起, 至第一个元素止,进行反复筛选v算法评价 l时间复杂度:最坏情况下 T(n)=O(nlog2n) l空间复杂度:S(n)=O(1) l稳定性:不稳定9数据结构计算机与信息学院 刘勇9.1 插入排序9.2 交换排序9.3 选择排序9.4 归并排序9.5 基数排序9.6 小结(各类排序方法比较)第第9 9章章 排序排序10数据结构计算机与信息学院 刘勇 归并将两个或两个以上的有序 表组合成一个新的有序表,叫 2-路归并排序v算法基本思路:设两个有序的子文件(相当于输 入堆)放在同一向量中相邻的位置上: Rlowm,Rm+1high,先将它们合并到 一个局部的暂存向量R1(相当于输出堆)中 ,待合并完成后将R1复制回Rlowhigh中 。 9.4 归并排序11数据结构计算机与信息学院 刘勇A.设置i,j和p三个指针,其初值分别指向这三个 记录区的起始位置;B.合并时依次比较Ri和Rj的关键字,取关键字 较小的记录复制到R1p中;C.然后将被复制记录的指针i或j加1,以及指向复 制位置的指针p加1。 D. 重复这一过程直至两个输入的子文件有一个 已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。 合并过程演示12数据结构计算机与信息学院 刘勇l设初始序列含有n个记录,则可看成n个有 序的子序列,每个子序列长度为1l两两合并,得到n/2个长度为2或1的有序 子序列l再两两合并,如此重复,直至得到一个 长度为n的有序序列为止排序过程13数据结构计算机与信息学院 刘勇例初始关键字: 49 38 65 97 76 13 27一趟归并后: 38 49 65 97 13 76 27二趟归并后: 38 49 65 97 13 27 76三趟归并后: 13 27 38 49 65 76 9714数据结构计算机与信息学院 刘勇算法实现void MergeSortDC(SeqList R,int low,int high) /用分治法对Rlowhigh进行二路归并排序int mid;if(lowhigh) /区间长度大于1 mid=(low+high)/2; /分解MergeSortDC(R,low,mid); /递归地对Rlowmid排序MergeSortDC(R,mid+1,high);/递归地对Rmid+1high排序Merge(R,low,mid,high); /组合,将两个有序区归并为一个有序区 /MergeSortDC15数据结构计算机与信息学院 刘勇void Merge (SeqList R,int low,int m,int high) /将两个有序的子文件Rlowm和Rm+1high归并成一个有序的 /子文件Rlowhighint i=low,j=m+1,p=0; /置初始值RecType *R1; /R1是局部向量,若p定义为此类型指针速度更快R1=(ReeType *)malloc(high-low+1)*sizeof(RecType);if(! R1) /申请空间失败Error(“Insufficient memory available!“);while(i=m&j=high) /两子文件非空时取其小者输出到R1p上R1p+=(Ri.key=Rj.key)?Ri+:Rj+;while(i=m) /若第1个子文件非空,则复制剩余记录到R1中R1p+=Ri+;while(j=high) /若第2个子文件非空,则复制剩余记录到R1中R1p+=Rj+;for(p=0,i=low;i=high;p+,i+)Ri=R1p;/归并完成后将结果复制回Rlowhigh /Merge16数据结构计算机与信息学院 刘勇v算法 描述v算法评价 l时间复杂度: T(n)=O(nlog2n) l空间复杂度:S(n)=O(n) 因 为需要一个辅助向量来暂存两有序子文件归并的结 果 l稳定性:稳定17数据结构计算机与信息学院 刘勇9.5 基数排序例 对52张扑克牌按以下次序排序: 23A23A 23A23A两个关键字:花色( )面值( 23A) 并且“花色”地位高于“面值” 多关键字排序 基数排序基本思路:基数排序不需要和前面的排序方法那样进行关 键字的比较和移动,它是一种借助多关键字排序的 思想对单逻辑关键字进行排序的方法。18数据结构计算机与信息学院 刘勇v多关键字排序方法l最高位优先法(MlD):先对最高位关键字k1(如花色)排 序,将序列分成若干子序列,每个子序列有相同的k1值;然后 让每个子序列对次关键字k2(如面值)排序,又分成若干更 小的子序列;依次重复,直至就每个子序列对最低位关键字 kd排序;最后将所有子序列依次连接成为一个有序序列. l最低位优先法(LlD):从最低位关键字kd起进行排序,然后再 对高一位的关键字排序,依次重复,直至对最高位关键字 k1排序后,便成为一个有序序列. l MlD与LlD不同特点 u按MlD排序,必须将序列逐层分割成若干子序列,然后对各 子序列分别排序 u按LlD排序,不必分成子序列,对每个关键字都是整个序列 参加排序;并且可不通过关键字比较,而通过若干次分配与 收集实现排序.19数据结构计算机与信息学院 刘勇 链式基数排序v基数排序:借助“分配”和“收集”对单逻辑 关键字进行排序的一种方法.单逻辑关键字可以看成由多个关键字复合而 成的,例如若关键字是数值,且都在0999之间,则 可以把每个十进制数字看成一个关键字,位权越高 的关键字优先程度越高。对应的基数就是关键字 的取值范围10。如果关键字由5个字母组成呢? 关键字可取5个,基数取26。 v链式基数排序:用链表作存储结构的基 数排序20数据结构计算机与信息学院 刘勇例初始状态:278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集:21数据结构计算机与信息学院 刘勇505008109930063269278083184589二趟收集:083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集:22数据结构计算机与信息学院 刘勇008063083109184269278505589930三趟收集:109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集:23数据结构计算机与信息学院 刘勇
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号