课程教案基本单元（ 6学时）.ppt

《课程教案基本单元（ 6学时）.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、课程教案基本单元（6学时）一、教学目的、基本要求（提出了解、熟悉及掌握的内容）：1.熟悉相关的基本概念、各种简单排序、希尔排序、快速排序、归并排序、堆排序算法思想。2.掌握各种简单排序、希尔排序、快速排序、归并排序、堆排序算法描述。3.了解基数排序等其他排序方法。二、重点、难点及突破方法1.重点是理解和掌握排序方法2.难点是希尔排序、快速排序、归并排序、堆排序方法的算法描述和算法性能分析3.突破方法：使用动画演示各种排序方法，并且进行随堂练习。课堂讲解并编写算法步骤、同时让学生模仿编写相关的算法。最后，留下一些问题让

2、有兴趣和有能力的同学深入钻研。第十章排序数据结构课程研究的内容1.数据的逻辑结构：线性结构、树形结构、图状结构2.数据的存储结构：顺序存储结构、链式存储结构3.操作：编写算法，讨论算法的性能等一、概念1.排序：将数据元素的任意序列重新排列成按关键字有序的序列。2.排序方法的稳定性：在待排序的序列中，存在两个记录Ri领先于Rj(i

3、序的记录存放在内存中进行的排序过程；外部排序：是指待排序的记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。4.排序算法的性能度量（1）排序算法的时间复杂度：记录移动次数、比较次数；（2）空间复杂度；（3）排序方法的稳定性二、插入排序1.直接插入排序：（1）基本操作：是将一个记录插入到已排好序的有序表中，从而得到一个新的记录数增1的有序表。（2）整个排序过程：先将原序列中的第一个记录看成是一个有序的子序列，然后，从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为

4、止。（3）算法描述：typedefintKeyType;typedefstruct{KeyTypekey;......;}Record;typedefstruct{Recordr[21];intlength;}SqList;/*r[0]闲置或用作哨兵单元*/voidInsertSort(SqList&L){for(i=2;i<=L.length;++i)if(L.r[i].key

5、-j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}//O(n*n)性能分析：（1）时间复杂度：O(n*n)（2）空间复杂度：O(1)（3）排序方法是稳定的直接插入排序算法作业typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;voidInsertSort(SqList&L){//不使用“哨兵”。for(i=___;i

6、____;--j);;}}//算法复杂度____________O(n*n)2.希尔排序（1）基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（2）希尔排序的特点：子序列的构成不是简单的“逐段分割”，而是，将(位置)相隔某个“增量”的记录组成一个子序列。（3）增量序列的选择：希尔取法：d[0]=n/2d[1]=d[0]/2......d[i+1]=d[i]/2...最后一个增量必须等于1每一个增量对应一趟希尔排序希尔

7、排序图解原始序列：d0=5,分割成5组一趟希尔排序结果d1=2,分割成2组二趟希尔排序结果d2=1,对全体记录进行一次直接插入排序三趟希尔排序结果顺序存储原始序列Shell算法描述voidShellSort(SqList&L){for(d=L.length/2;d>=1;d=d/2)for(i=d+1;i<=L.length;i++)//完成一趟Shell排序if(L.r[i].key0&&L.r[0].key<

8、L.r[j].key;j-=d)L.r[j+d]=L.r[j];//数据向后搬移L.r[j+d]=L.r[0];//插入}}//ShellSortend性能分析：时间复杂度：O(n)；空间复杂度：O(1)；Shell排序方法不稳定；3/2一趟Shell排序算法的另一种描述voidShellInsert(SqList&L,intd){for(k=