3_一级指导教师教案_数据结构2

4、Shell排序算法基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。特点：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。用Shell排序法排序，第一次的增量取n/2，以后的增量为前一次的一半，直到增量为1时排序完成。算法复杂度：O(n3/2)Shell排序举例（非稳定的）二趟结果{13，04，49，38，27，49，55，65，97，76}增量取1：13，04，49，38，27，49，55，65，97，76三趟结果{04，13，27，38，49，49，55，65，76，97}一趟结果{13，27，49，55，04，49，38，65，97，76}增量取3：13553876270465494997例：{49，38，65，97，76，13，27，49，55，04}增量取5：491338276549975576045、堆排序堆的定义：n个元素的序列{k1,k2,...,kn}当且仅当满足下列条件时，称之为堆。ki=k2iki=k2iki=k2i+1ki=k2i+1或(i=1,2,...,[n/2])堆举例：{96,83,27,38,11,09){12,36,24,85,47,30,53,91}9683381109271236854730245391堆可以看成是一棵完全二叉树结点的层次序列,且所有非叶结点的值均不大于(或不小于）左、右孩子结点的值堆排序的基本思想：对一组待排序的关键码，首先把它们按堆的定义排列成一个序列（称为建堆），这就找到了最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复进行，直到将全部关键码排好序为止。根结点是堆中的最小元素。实现堆要解决的问题1、如何从一个无序序列建成一个堆？2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？例：图a是个堆，假设输出堆顶元素之后，以堆中最后一个元素代之，如图b。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。1236854730245391(a)9136854730245312(b)2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？首先以堆顶元素和其左、右子树根结点的值比较之，由于右子树根结点的值小于左子树根结点的值且小于根结点的值，则将24和91交换之；由于91替代了24之后破坏了右子树的堆，则需要进行和上述相同的调整，直至叶子结点;重复上述过程，将堆顶元素91和堆中最后一个元素30交换且调整，得到如图d所示新的堆。称这个自堆顶至叶子的调整过程为“筛选”。91368547302453(c)24368547913053(d)PROCsift（VARr:listtype;k,m:integer）;{假设r[k+1..m]中各元素满足堆的性质，本算法调整r[k]使整个序列r[k..m]中各元素满足堆的性质}i:=k;j:=2＊i;x:=r[k].key;finished:=fakse;t:=r[k];{暂存“根”记录r[k]}WHILE(j=m)ANDNOTfinishedDO[IF(jm)AND(r[j].Keyr[j+1].Key)THENj:=j+1;{若存在右子树，且右子树根的关键字小，则沿右分支“筛选”}IFx=r[j].KeyTHENfinished:=true{筛选完毕}ELSE[r[i]:=r[j];i:=j;j:=2＊i]{继续筛选}]r[i]:=tENDP;{SIFT}1、从无序序列建成一个堆从一个无无序序列建成一个堆的过程就是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第[n/2]个元素，由此“筛选”只需从第[n/2]个元素开始。例：图a中的二叉树表示一个有8个元素的无序序列{49，38，65，97，76，13，27，49}筛选从第4个元素开始，由于9749,则交换之，交换后的序列如图b所示；49389776132749(a)654938497613652797(b)同理，在第3个元素65被筛选之后序列的状态如图c所示。由于第2个元素38不大于其左、右子树根的值，则筛选后的序列不变。图e所示为筛选根元素49之后建成的堆。4938497665132797(c)4938497665132797(d)1338497665274997(e)堆排序算法：PROCheapsort（VARr:listtype）；{r[1..n]对进行堆排序，执行本算法后，r中记录按关键字从大到小有序排列}FORi:=[n/2]DOWNTO1DOsift（r,I,n）;{自第[n/2]个记录开始进行筛选建堆}FORi:=nDOWNTO2DO[r[1]〈－〉r[i];{将堆顶记录和堆中最后一个记录互换}sift（r,1,i-1）{调整r[1]使r[1..i-1]变成堆}]ENDP;6、基数排序(RadixSorting)不需要进行关键字之间的比较借助多关键字排序的思想对单关键字排序6、1多关键字排序例：已知扑克牌中52张牌面的次序关系为：2345678910JQKA2345678910JQKA2345678910JQKA2345678910JQKA每一张牌有两个“关键字”：花色()和面值(23...A)且花色()优先于面值(23...A)最高位优先(MSD)法:分成子序列分别排序最低位优先(LSD)法:通过若干次“分配”和“收集“6、2链式基数排序借助“分配”和“收集“两种操作对单关键字进行排序。例:首先以静态链表存储n个待排记录，并令表头指针指向第一个记录，如下：-278-109-063-930-589-184-505-269-008-083a初始状态6、2链式基数排序第一趟分配对最低位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至10个链队中去，每个队列中的记录关键字的个位数相等，如下图01324567892781090639301845055892690080836、2链式基数排序第一趟收集是改变所有非空队列的尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列中的记录链成一个链表，如下图；-930-063-083-184-505-278-008-109-589-269c第一趟收集之后第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如下图d-g0132456789278109063930184505589269008184505-008-109-930-063-269-278-083-184-589e第二趟收集之后0132456789505008109930063269278083083589008-063-083-109-184-269-278-505-589-930g第三趟收集之后的有序文件7、教师:根据算法，同学们开始编写程序；同组同学可以互相交流。（设计思想：巩固新知，协作学习）学生：上机操作，编写程序。学生：继续编写、调试程序。学生：上机操作，修改程序。首先，在计算机编程中排序是一个经常遇到的问题。数据只有经过排序后，才更有意义。其次，排序算法说明了许多重要的算法的技术，例如二进制细分，递归和线性添加。最后要说明的一点是不同的算法有不同的优缺点，没有一种算法在任何情况下都是最好的算法。为什么有这么多的排序算法?8、教学小结，知识升华（时间分配：1分钟）9、布置作业，巩固新知（时间分配：1分钟）①课本P189；②继续完善程序。10、学生关机，结束教学（时间分配：1分钟）