(8.3.1)--(24)《数据结构》教案.pdf

《(8.3.1)--(24)《数据结构》教案.pdf》由会员分享，可在线阅读，更多相关《(8.3.1)--(24)《数据结构》教案.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 第第8章章 内部排序内部排序(共共 6 时时，包括实训内容包括实训内容)课题课题 8.3 交换排序 8.4 选择排序 理论理论课时课时 1 学时 实实训训课时课时 1 学时 教学内容教学内容 起泡排序、快速排序、简单选择排序、树形选择排序、堆排序 教学目标教学目标 掌握交换排序、选择排序的常用排序方法 教学重点教学重点 起泡排序、快速排序、简单选择排序、树形选择排序 教学难点教学难点 快速排序、树形选择排序、堆排序 教学教学活动及主要活动及主要内容内容 学生活动学生活动 一、创设一、创设情境情境，导入新课（，导入新课（2 分钟）（分钟）（直接导入法直接导入法）导入：前面我们学习了插入排序

2、，其实还有很多排序的方法比如交换排序、选择排序，那么这两种排序的具体过程是什么样的？效率会不会更高？下面我们来学习交换排序、选择排序。二、新课二、新课讲解讲解（共共计计 16 分钟）（讲解法、提问法、分钟）（讲解法、提问法、演示演示法）法）8.3 8.3 交换排序交换排序 1.起泡排序起泡排序(bubblesort)(1)起泡排序的基本思想 从序列的第 1 条记录开始，将相邻的两条记录关键字进行比较，遇反序则交换相应的记录位置。n 个记录参与排序时，至多要进行 n-1 趟，其中每一趟都会将当前序列的关键字最大值记录交换到所在的位置。2)起泡排序算法 void BubbleSort1(SortL

3、ist*L)int i,j;ElemType t;for(i=1;ilength;i+)/*排序趟数*/for(j=1;jlength-i;j+)/*每趟比较的次数*/if(L-rjL-rj+1)/*若出现逆序,则交换*/t=L-rj;L-rj=L-rj+1;L-rj+1=t;【例【例 87】已知整数序列70，83，100，65，10，32，7，65，9，请给出采用起泡排序法对该序列做升序排列的排序的过程。排序过程如图 8.9 所示 激 发 学 生学习交换排序、选 择 排 序的兴趣。学 生 应 掌握起 泡 排 序的思 想 和 算法并动手练习 2 图 8.9 起泡排序示例 由此看出，通过比较相邻

4、的两条记录关键字，关键字小的记录像气泡一样上升，关键字大的记录像石头一样下沉故称为起泡排序。(3)算法分析。比较的次数为(n-1)+(n-2)+(n-(n-1)(n-1)(n-1)+(n-(n-1)/2n(n-1)/2，因此，T(n)=O(n)。2快速排序快速排序 快速排序是霍尔发明的，因此又称霍尔排序霍尔排序(Hoare sort)。(1)基本思想 将每一条记录定位到指定的位置上。实质上，就是将序列中的某条记录当成一个标尺，凡是比该记录关键字小的记录移到该记录的前面，不小于该记录关键字的记录移到该记录的后面。这样就确定了该记录的位置，也称该记录为“枢轴记录”。通常，将待排序记录序列中的第 1

5、 条记录定为枢轴记录。反向扫描到比枢轴记录关键字小的记录，与枢轴记录交换位置，再正向扫描到比枢轴记录关键字大的记录，与枢轴记录交换位置，如此进行，直到找到枢轴记录确定的位置为止。再对未排序的子序列分别进行快速排序，直到所有记录均完成定位。从上述分析可以看出快速排序是递归的。(2)快速排序算法 void HoareSort(SortList*L,int low,int high)int i,j;if(lowr0=L-ri;/*暂存枢轴记录*/while(ij)while(irj=L-r0)j-;/*反向定位移动的记录位置*/L-ri=L-rj;while(irir0)i+;/*正向定位移动的记录

6、位置*/L-rj=L-ri;L-ri=L-r0;/*将枢轴记录存入指定位置*/HoareSort(L,low,i-1);/*对排在枢轴记录前面的记录快速排序*/HoareSort(L,i+1,high);/*对排在枢轴记录后面的记录快速排序*/void QuickSort(SortList*L)/*对所有记录进行快速排序*/学 生 要 掌握快 速 排 序的算 法 并 动手实践 3 HoareSort(L,1,L-length);例【例【8.8】已知整数序列70，83，100，65，10，32，7，65，9，请给出采用快速排序法对该序列做升序排列的排序的过程。快速排序示例(3)算法分析 在每一趟

7、快速排序中，关键宇比较的次数和移动的次数均不超过 n，时间性能主要取决于递归的深度，而深度是与记录初始序列有关的。最坏情况是初始序列已基本有序，则递归的深度接近于 n，算法时间复杂性 T（n）=O（n）。8.4 选择排序选择排序 1.简单选择排序简单选择排序 1)基本思想 一趟简单选择排序（simple selection sort）的操作为，从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。4 2)简单选择排序的算法 void SelectSort1(SortList*L)int i,j;ElemType t;for(i=1;ilength;i+)/*排序趟数*/for(j=i+

8、1;jlength;j+)/*每趟比较的次数*/if(L-riL-rj)/*若逆序，则交换*/t=L-ri;L-ri=L-rj;L-rj=t;为了避免过多的交换记录，可以用一个指针指向最小关键字所在单元，一趟比较结束后再将该记录交换到指定位置。改进的算法如下：void SelectSort2(SortList*L)int i,j,k;ElemType t;for(i=1;ilength;i+)/*排序趟数*/for(k=i,j=i+1;jlength;j+)/*每趟比较的次数*/if(L-rkL-rj)k=j;/*比较并保存关键字小的元素下标*/if(k!=i)/*若不是当前记录，则交换*/t

9、=L-rk;L-rk=L-ri;L-ri=t;例【例【8.9】已知整数序列70，83，100，65，10，32，7，65，9，请给出采用简单选择排序法对该序列进行升序排序的过程。排序过程如图 8.11 所示 图 8.11 简单选择排序示例 3）算法分析 简单选择排序算法的比较次数与记录序列的初始状态无关，比较的次数为(n-1)+1)/2n(n-1)/2，即 O（n）。移动的次数与记录序列的初始状态有关，若记录序列是基本有序的，则移动次数接近于 0，即 O(1)，若记录序列是反序的，则移动次数接近于 3n(n-1)/2，即 O（n2）。因此，简单的选择排序算法的时间性能 T（n）=O（n）。空间

10、上，只需要一个交换变量用的临时空间，即 S（n）=O（1）。选择学 生 应 掌握简 单 选 择排序 的 思 想和算 法 并 动手练习 5 排序算法是不稳定的排序方法。2.树树形形选择排序选择排序 1)基本思想 树形选择排序使用近似于完全二叉树的树形，所有记录均为叶子结点，从叶子结点开始，通过两两比较填到树顶的结点是对应关键字最小的记录，然后将该叶子结点关键字置成最大关键字（或无穷大），继续选出第二个最大值。如此重复进行，直到排序结束。2)树形选择排序算法 SortList CreInitTree(SortList*L)/*建初始树形*/int i;SortList Q;/*临时变量，存储完全二

11、叉树*/Q.length=2*L-length-1;/*该完全二叉树的结点数 2n-1*/for(i=L-length;iri-L-length+1;/*将已知记录序列存为叶子结点*/for(i=L-length-1;i=1;i-)/*根据锦标赛过程建完全二叉树*/Q.ri=(Q.r2*ir1;for(i=2;ilength;i+)if(mri)m=L-ri;return m;void TreeSort(SortList*L)int i,j;SortList Q;ElemType m;m=Max(L);Q=CreInitTree(L);/*建初始树形*/L-r1=Q.r1;/*第一个最小记录存

12、入单元 1 中*/for(i=2;ilength;i+)j=1;while(jlength)/*找刚刚存入的最小记录所在的叶子结点*/j=(Q.r2*j1)/*再找叶子结点的最小关键字所对应的记录*/j=j/2;Q.rj=(Q.r2*jri=Q.r1;/*将该最小记录存入指定单元*/例【例【8.10】已知整数序列70，83，100，65，10，32，7，65，9，请给出采用树形选择排序法对该序列做升序排列的排序的过程。学 生 应 掌握树 形 选 择排序 的 过 程和算 法 并 动手练习 6 排序过程如图 8.12 所示 a 图 7.12 树形选择排序示例 3)算法分析 由于树结点个数为 2n-

13、1，建初始二叉树的时间性能为 T（n）=O（n）；查找选择其余最小关键字结点进行的比较次数及记录的移动次数为 2(log2(2n-1)+1)n，所以，时间性能 T（n）=nlog2n。空间上，该算法需要 2n-1 个辅助的记录空间，所以，空间性能 S（n）=O（n）。若一个结点的左，右孩子结点关键字值相等，则该结点的值可以选择其左，右孩子结点中的任意一个，所以，树形选择排序算法是不稳定的排序方法。3.堆排序堆排序 (1)基本思想。堆排序就是利用堆的特性对记录序列进行排序的一种方法。具体作法是：先建一个大顶堆，即先选择一个关键字为最大的记录，然后与序列中最后一个记录交换，再对序列中前 n-l 条

14、记录进行“筛选”，重新将它调整成为一个大顶堆，再将堆顶记录和第 n-1 个记录交换。如此反复进行，直至所有元素都安排完为止。学 生 应 掌握堆 排 序 的过程 和 算 法并动手练习 7 实质上，堆排序就是由建初始堆和调整建堆(筛选)两个过程组成。在此，所谓筛选是指对一棵左、右子树均为堆的完全二叉树，经调整根结点后使之成为堆的过程。建堆时一定要从最后一个非叶子结点开始。(2)堆排序算法 堆排序的关键是调整建堆，建初始堆时也是要从最后个非叶子结点开始向根结点方向进行调整建堆。假设完全二叉树的第 i 个结点的左子树、右子树已是堆，则对第 i 个结点进行调整时，需要将 r2i与 r2i+1之中的最大者

15、与 ri进行比较，若 ri较小则与之交换。这有可能破坏下一级的堆，因此，需要继续采用上述方法调整构造下一级的堆。如此重复。直到将以第 i 个结点为根的子树构成堆为止。调整建堆算法。void AdjustTree(SortList*L,int n,int k)/*n 为最大下标值，k 为调整点下标*/int i,j;i=k;j=2*i;L-r0=L-ri;while(j=n)/*沿关键字较大的孩子结点向下筛选*/if(jrj+1L-rj)j=j+1;/*j 为 i 的孩子结点中关键字值较大的记录的下标*/if(L-r0L-rj)break;L-ri=L-rj;/*将 rj调整到双亲结点位置上*/

16、i=j;j=2*i;L-ri=L-r0;/*定位完成*/堆排序算法：void AdjustTree1(SortList*L,int n,int k)/*n 为最大下标值，k 为调整点下标*/int i,j;ElemType t;i=k;j=2*i;while(j=n)/*沿关键字较大的孩子结点向下筛选*/if(jrj+1L-rj)j=j+1;/*j 为 i 的孩子结点中关键字值较大的记录的下标*/if(L-riL-rj)break;/*筛选结束*/else t=L-ri;L-ri=L-rj;L-rj=t;/*将 rj调整到双亲结点位置上*/i=j;j=2*i;/*继续向下筛选*/3）算法分析

17、对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为 2(k-1)；对 n个记录，建成深度为 log2n+1 的堆，所需进行的关键字比较的次数至多为 4n；调整“堆顶”n-1 次，总共进行的关键字比较的次数不超过 2(log2(n-1)+log2(n-2)+log22)2n（log2n）。因此，堆排序的时间性能 T(n)O(nlog2n)。空间上，只需要一个记录的辅助空间，因此 S(n)O(1)，堆排序算法是不稳定的排序方法。8 课堂思政：课堂思政：学习学习归并排序归并排序和和计数排序计数排序，要善于总结排序方法，抓住问题关键要善于总结排序方法，抓住问题关键。三三、归纳总结，再度提升归纳总结，再度提升（1 分钟）（讲解法）分钟）（讲解法）1.起泡排序 2.快速路径 3.简单选择排序 4.树形选择排序 5.堆排序 四四、作业作业，预习任务预习任务（1 分钟）（激趣法）分钟）（激趣法）课后习题 P247，习题 8：交换排序、选择排序相关习题。预习：8.5 归并排序8.6 计数排序 学 生 记 录作业 和 预 习内容。9 板 书 设 计 第第 8 8 章章 内部排序内部排序 8.3 8.3 交换排序交换排序 1.起泡排序 2.快速排序 8.4 选择排序选择排序 1.简单选择排序 2.树形选择排序 3.堆排序