教师发展中心名师范课程听课记录（五）

《教师发展中心名师范课程听课记录（五）》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、教师发展中心名师示范课程听课记录（五）何钦铭：排序与哈希查找教学主题排序与哈希查找课堂性质计算机及相关专业专业基础课授课对象计算机学院本科生，观摩师生授课教师何钦铭教授职称计算机科学与技术学院系统结构与网络安全研究所博导上课时间2012年11月2日8:00-9:35上课地点紫金港校区东1B-308内容提要：（1）大数据排序、排序最坏时间复杂性下限以及基数排序。解决大数据结构对象的排序问题有两个要点，一是记录对象的下标，排序时不交换对象本身而是交换对象下标；二是通过环形移动恢复排序好的下标序列为对象序列。基于比较和交换的排序算法的最坏时间复杂性下线是nlogn。基数排序

2、是基于多键码的排序算法。使用排序算法要考虑它的时间复杂性、稳定性和空间复杂性。（2）哈希查找。面对动态的数据集合，要使用动态查找方法，哈希查找是一种解决动态查找问题的算法。哈希查找有两个要点，一是构造分布均匀的映射函数，二是想办法解决可能的冲突。函数设计和冲突解决有多种方法，因此必须考虑它们的有效性。教学片断纪实NotesP1：PPT页码第一部分：排序P1：复习归并排序和快速排序，这两个算法的基本思想都是基于分治法的思想：把大问题分解为小问题来解决，比如对n个数据分成两堆，对这两堆数据分别进行排序，对两堆进行排序后可以递归做，再把两堆从小到大的数据合在一起，变成原数据

3、从小到大排列的结果。最核心的步骤有三步：分解数据、递归、合并解，最主要的步骤是第一步和第三步。两个典型算法的区别是分解问题的方法不同。归并排序是自然地将元素分为数量相等的两部分，分别完成每一部分的排序后再合并。快速排序，每一步基于一个元素（基准元素）将所有元素分为较大的部分和较小的部分，对这两部分分别进行排序。所以两者的区别是重点不同，快速排序的重点在于怎么分解问题，而归并排序的重点放在第三步。P2：大数据结构对象的排序排序的基本特征就是对象之间的比较，发现位置不对就发生交换，所以比较和交换是之前的排序算法中的基本操作。在这种排序过程中会碰到一个问题，如果排序的对象很

4、大，因为对象可能不仅仅是一个整数，可能代表了一个对象的信息，这个对象信息就是一个结构，也许是几十K的规模。而在排序中我们频繁地发生交换，经常把东西挪来挪去，光挪动的动作会产生很大代价。所以提出一个问题，对大结构的对象排序，有没有特殊的考虑？教学智慧捕捉简要总结已学过的两种排序算法提出问题比如说在医院排队的例子：不是每个人都站在门口排队，使用病历卡或挂的号排队，也就是排队不需要对象本身去排队，那个号拿来排队就可以了。不需要把大的对象不断交换、记录对象的位置，在排序过程中，只交换所记录的位置，排序结束后再一次性完成对大数据的移动交换。详细讲述如何通过记录对象在数组中的位置

5、进行排序，以及对标号排序结束后如何以比较低的代价将大的数据移动至恰当的位置。关于这个问题基本思路的要点是两个，一个是大对象排序的时候不是把对象本身挪来挪去，而是把对象的下标挪来挪去；第二个就是，怎么把下标恢复到对象的序列，方法就是一个环，先把其中一个对象的位置腾出来，再循环挪动。比方说医院B超排队，很多人早到了，护士来的时候发现十张椅子已经坐满人了，这个时候他要决定一个顺序，这10个人里我应该怎么排队？所以他想出一个办法，按年纪大小进行排队。那么他首先根据病历卡上的年龄给病人排个队，先把第一个位置腾出来，年纪最大的坐那里，然后看年纪最大的那个人的位置应该是谁坐的，然后

6、那那个人在坐过去，然后再看腾出来的位置应该是谁坐的，再坐过去。这样的话每个人只要挪一次就可以到位了。动画演示。P3：基于比较和交换的排序算法的时间复杂度下限排序算法有这么两大类，第一类是简单排序，比方说插入排序、选择排序、冒泡排序，它的时间复杂性基本是到n的平方。还有一类包括希尔排序、快速排序、归并排序、堆排序，这四类的时间复杂性基本是到nlogn的范围。所以接下来的问题，我们的排序算法有没有可能做得更好，有没有可能把这个算法的时间复杂性再提高。当然底线是，每个数据看一遍就要n了。这是很多人都想要做到的，但实际上做不到。可以证明基于比较和交换的算法最坏情况下至少需要n

7、logn。怎么证明？任何一个算法都是决策的过程，都可以用决策树来看。这是在计算机领域里面分析问题很有名的方法。举一个一个简单的例子，比如插入排序，三个元素k0,k1,k2，呈现通过决策树排序的过程。如果n个元素进行排序，决策树的叶节点个数是多少？（学生：n阶乘）那么，树高多少？（学生：nlogn）那么这是最大值还是最小值？（学生：至少）对，平衡的时候是最矮的时候。也就是决策树里面一定存在一条路径时间复杂性要超过nlogn。提出了排序算法稳定性的概念：比如两个一样的数，输入的时候哪个数在前，最后出来的时候还是谁在前面。按照是否稳定的标准对插入排序（稳定