数据结构第24次课 排序C

《数据结构第24次课 排序C》由会员分享，可在线阅读，更多相关《数据结构第24次课 排序C（47页珍藏版）》请在金锄头文库上搜索。

1、数据结构计算机与信息学院 刘勇每课一贴： 古之立大事者,不惟有超世之才,亦必有 坚忍不拔之志。 苏轼有志者,事竟成,破釜沉舟,百二雄关终属楚；苦心人,天不负,卧薪尝胆,三千越甲可吞吴。 蒲松龄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 交换排序(通过

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的冒泡排序.在“自下向上”冒泡排序每趟扫描中,记 住最后一次交换发生的位置las

3、tExchange,(该 位置之前的相邻记录均已有序).下一趟排序开 始时,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(R

4、j+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最坏情况（每次总是选到

5、最小或最大元素作枢轴） 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 方法：输出堆顶元素之后,以堆中最后一个元素替代之；然 后将根结点值与左、

6、右子树的根结点值进行比较,并与其中小 者进行交换；重复上述操作,直至叶子结点,将得到新的堆,称 这个从堆顶至叶子的调整过程为“筛选”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数据结构计

7、算机与信息学院 刘勇 归并将两个或两个以上的有序 表组合成一个新的有序表,叫 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. 重复这一过程直至两

8、个输入的子文件有一个 已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到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 971

9、4数据结构计算机与信息学院 刘勇算法实现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

10、(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.

11、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张扑克牌按以

12、下次序排序： 23A23A 23A23A两个关键字：花色（ ）面值（ 23A） 并且“花色”地位高于“面值” 多关键字排序 基数排序基本思路：基数排序不需要和前面的排序方法那样进行关 键字的比较和移动,它是一种借助多关键字排序的 思想对单逻辑关键字进行排序的方法。18数据结构计算机与信息学院 刘勇v多关键字排序方法l最高位优先法（MlD)：先对最高位关键字k1（如花色）排 序,将序列分成若干子序列,每个子序列有相同的k1值；然后 让每个子序列对次关键字k2（如面值）排序,又分成若干更 小的子序列；依次重复,直至就每个子序列对最低位关键字 kd排序；最后将所有子序列依次连接成为一个有序序列. l

13、最低位优先法(LlD)：从最低位关键字kd起进行排序,然后再 对高一位的关键字排序,依次重复,直至对最高位关键字 k1排序后,便成为一个有序序列. l MlD与LlD不同特点 u按MlD排序,必须将序列逐层分割成若干子序列,然后对各 子序列分别排序 u按LlD排序,不必分成子序列,对每个关键字都是整个序列 参加排序；并且可不通过关键字比较,而通过若干次分配与 收集实现排序.19数据结构计算机与信息学院 刘勇 链式基数排序v基数排序：借助“分配”和“收集”对单逻辑 关键字进行排序的一种方法.单逻辑关键字可以看成由多个关键字复合而 成的,例如若关键字是数值,且都在0999之间,则 可以把每个十进制

14、数字看成一个关键字,位权越高 的关键字优先程度越高。对应的基数就是关键字 的取值范围10。如果关键字由5个字母组成呢？ 关键字可取5个,基数取26。 v链式基数排序：用链表作存储结构的基 数排序20数据结构计算机与信息学院 刘勇例初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：21数据结构计算机与信息学院 刘勇505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：22数据结构计算机与信息学院 刘勇008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：23数据结构计算机与信息学院 刘勇