《排序.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算法，采用混合
6、算法： 在数据量少的时候，算法转入插入排序; 其它情况下则优先采用快速排序; STL还对快速排序算法的补充：快速排序的特点是平均性能好，能达到O(NlgN)的性能，缺点是对于最坏情况性能会下降到O(N2)。STL对此做的补充是引入一个递归计数，当递归深度超过一定阈值，则算法转入一个相对较慢但最坏情况也是O(NlgN)的算法，比如堆排序。这一算法监控自身的递归深度，具有一定的内观性，被称为内观排序(introsort - introspective sort)，实际上是快速排序的变种，是一种混合算法。在最坏情况下能近似达到O(NlgN)的性能。实际上在最坏情况下比堆排序要差点，但是比快速排序要好
7、得多。而其平均性能和快速排序差不多。 stable_sort 采用归并排序。 partial_sort 采用堆排序。,#include / 头文件 struct Item int key; char* otherinfo; ; bool cmp(Item a, Item b) return a.keyb.key ; Item R100; / 排序区间为 first, last) sort (R , R+100, cmp); / 对全部元素进行排序 sort (R , R+10, cmp); / 对前10个元素进行排序 stable_sort (R , R+100, cmp); / 对全部元素进
8、行稳定排序,int A12 = 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5; partial_sort(A, A + 5, A + 12); / 处理范围是全部12个元素，但排序的结果只能保证最小的5个元素都已经在合适的位置（即，分别位于A04），而后面的元素则不保证有序,采用堆排序的思想 / 排序结果为： “1 2 3 4 5 11 12 10 9 8 7 6 ” - int A12 = 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5; nth_element(A, A + 6, A + 12); / 处理范围是全部12个元素，但处
9、理的结果只保证第7小的元素在合适的位置（即，位于A6），而其它的元素之间则不保证有序。 / 排序结果为： “5 2 6 1 4 3 7 8 9 10 11 12” / 本函数的时间复杂度约为O(N), 效率非常高，采用快速排序的分区思想实现，而且还保证前面的6个元素均小于第7 个元素，而后面的N-7个元素均大于第7 个元素，,#include / 头文件 struct Item int key; char* otherinfo; ; bool cmp(Item a, Item b) return a.keyb.key ; Item R100; / 排序区间为 first, last) sort
10、 (R , R+100, cmp); / 对全部元素进行排序 sort (R , R+10, cmp); / 对前10个元素进行排序 stable_sort (R , R+100, cmp); / 对全部元素进行稳定排序,本章小结,1、熟悉各种（类）排序方法的特点及相应的时间、空间复杂度。 2、了解STL中的相关排序算法。,本章要求：,课后建议： HDoj 1872（stable_sort） HDoj 1280, 1425（partial_sort） HDoj 1157, 1939（nth_element） HDoj 1509, 1873,1434（用二叉堆实现优先队列） 较为熟练地利用堆的相关算法(优先队列)解决实际问题 熟悉STL之优先队列 priority_queue （头文件 queue） 熟悉STL之heap相关方法make_heap等 （头文件 algorithm） 尝试利用优先队列实现haffman树,