数据结构课件第九章排序幻灯片.ppt

一、时间性能 1. 平均的时间性能 基数排序 时间复杂度为 O(nlogn)： 快速排序、堆排序和归并排序 时间复杂度为 O(n2)： 直接插入排序、起泡排序和 简单选择排序 时间复杂度为 O(n): 2. 当待排记录序列按关键字顺序有序时 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 直接插入排序和起泡排序能达到O(n)的时间复杂度， 快速排序的时间性能蜕化为O(n2) 。 二、空间性能 指的是排序过程中所需的辅助空间大小 1. 所有的简单排序方法(包括：直接插入、 起泡和简单选择) 和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间； 3. 归并排序所需辅助空间最多，其空间复杂度为 O(n); 4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 排序之前 : { · · · · · Ri(K) · · · · · Rj(K) · · · · · } 排序之后 : { · · · · · Ri(K) Rj(K) · · · · ·· · · · · } 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的; 若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序、堆排序和希尔排序是不稳定的排序方法。 例如 : 对 { 4, 3, 4, 2 } 进行快速排序， 得到 { 2, 3, 4, 4 } 四、关于“排序方法的时间复杂度的下限” 本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法。 可以证明， 这类排序法可能达到的最快的时间复杂度为O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。) 例如:对三个关键字进行排序的判定树如下： K1K3 K1K2 K1K3 K2K3 K2 K3 K2K1K3 K1K2K3 K3K2K1 K2K3K1 K3K1K2 K1K3K2 １．树上的每一次“比较”都是必要的; ２．树上的叶子结点包含所有可能情况。 一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于?log2(n!)? +1, 则对 n 个关键字进行排序的比较次数至少是 ?log2(n!)? ? nlog2n (斯蒂林近似公式)。 所以，基于“比较关键字”进行排序的 排序方法，可能达到的最快的时间复杂度为 O(nlogn)。 10.8 外 部 排 序 一. 问题的提出 １．待排序的记录数量很大，不能一次装入内存，则无法利用前几节 讨论的排序方法 (否则将引起频繁访问内存)； ２．对外存中数据的读/写是以“数据块” 为单位进行的； 读/写外存中一个“数据块”的数据所需要的时间为： TI/O = tseek + tla + n? twm 其中 tseek 为寻查时间(查找该数据块所在磁道) tla 为等待(延迟)时间 n? twm 为传输数据块中n个记录的时间。 １．按可用内存大小，利用内部排序 方法，构造若干( 记录的) 有序子序列，通常称外存中这些记录有序子序列为 “归并段”； 二、外部排序的基本过程 由相对独立的两个步骤组成： ２．通过“归并”，逐步扩大 (记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。 例如：假设有一个含10,000个记录的磁盘 文件，而当前所用的计算机一次只 能对1000个记录进行内部排序，则 首先利用内部排序的方法得到10个 初始归并段，然后进行逐趟归并。 假设进行2?路归并(即两两归并)，则 第一趟由10个归并段得到5个归并段； 最后一趟归并得到整个记录的有