排序.ppt
《排序.ppt》由会员分享,可在线阅读,更多相关《排序.ppt(18页珍藏版)》请在三一文库上搜索。
1、8 排序(4),教学目标,1、掌握排序的概念,常用排序的方法及特点,并能进行时间复杂度、空间复杂度及算法稳定性的分析; 2、掌握插入排序、冒泡排序、选择排序、希尔排序的方法、算法; 3、掌握快速排序、堆排序、归并排序、基数排序的方法; 4、基本掌握快速排序、堆排序、归并排序的算法思想。 5、熟悉各种(类)排序方法的特点及相应的时间、空间复杂度。 6、了解STL中的相关排序算法。,8.1 概述 8.2 插入排序 8.3 交换排序 8.4 选择排序(堆排序) 8.5 归并排序 8.6 基数排序 8.7 各种排序方法的综合比较 8.8 STL与排序,教学内容,8.7 各种排序方法的综合比较,从平均时
2、间复杂度考虑,快速排序法的平均速度最快(这也是实践中大量采用快速排序的原因); 从最坏的时间复杂度考虑,快速排序为(n2),这一点不如堆排序和归并排序; 当 n 较大时归并排序可能比堆排序快,但归并排序需要很大的辅助空间; 朴素排序算法中直接插入排序最简单,当序列中的记录“基本有序”或n值较小时,可以优先选用直接插入排序。这种排序算法也常常与其他排序方法结合使用(例如,一些实用快速排序算法在划分出的分段很短时,通常转而用插入排序);当序列接近有序时,直接插入排序速度很快;,稳定性:大部分时间复杂度为O(n2)的简单排序法都是稳定的,大部分时间性能较好的排序都是不稳定的。一般来说,排序过程中的比
3、较是在相邻的两个记录关键字之间进行的排序方法是稳定的。稳定性由方法本身决定,不稳定的方法总能举出使其不稳定的实例; 基数排序最适合n很大而关键字较小的序列; 所有的简单排序方法(包括:直接插入、冒泡和简单选择) 和堆排序的空间复杂度为O(1);快速排序为O(log n),这是递归程序执行过程中,栈所需的辅助空间;归并排序所需辅助空间最多,其空间复杂度为 O(n);,关于“排序方法的时间复杂度的下限” 本章讨论的各种排序方法,除基数排序外,其它方法都是基于“比较关键字”进行排序的排序方法。可以证明,这类排序法可能达到的最快的时间复杂度为O(nlogn)。 由于基数排序不是基于“比较关键字”的排序
4、方法,所以它不受这个限制。,例如:对三个关键字进行排序的判定树如下:,K1K3,K1K2,K1K3,K2K3,K2 K3,K2K1K3,K1K2K3,K3K2K1,K2K3K1,K3K1K2,K1K3K2,树上的每一次“比较”都是必要的;,树上的叶子结点包含所有可能情况。,一般情况下,对n个关键字进行排序,可能得到的结果有n! 种,由于含n! 个叶子结点的二叉树的深度不小于log2(n!) +1, 则对 n 个关键字进行排序的比较次数至少是 log2(n!) nlog2n (斯特林(Stirling)公式近似公式)。 所以,基于“比较关键字”进行排序的排序方法,可能达到的最快的时间复杂度为 O
5、(nlogn)。,网址: http:/zh.wikipedia.org/wiki/斯特林公式,8.8 STL与排序,sort stable_sort partial_sort nth_element,make_heap(建堆) push_heap(插入) pop_heap(删除) sort_heap(堆排序),关于heap相关的操作方法,建议课后自学,STL在它的排序算法方面做了哪些优化呢? 自从快速排序算法出世以后,从平均性能上来说,除了在数据量极少(=20)的的情况下其性能不如插入排序外,快速排序算法的性能起码是其他同阶算法的2到3倍,这已经是不争的事实。 STL中的sort算法,采用混合
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序
链接地址:https://www.31doc.com/p-2607070.html