第9章排序资料.ppt

例如，若关键字是数值，且其值都在0? k?999范围内，则可把每一个十进制数字看成一个关键字，即可认为K由三个关键字（ K0， K1， K2 ）组成，其中K0是百位数， K1是十位数，K2是个位数； 又若关键字K由五个字母组成的单词，则可看成是由五个关键字（ （K0， K1， K2 ，K3，K4 ）组成，其中K j-1是（自左至右）的第j+1个字母。 1、C 2、A 3、C 4、D 1、4 2、快速 归并 3、快速 堆 * * 算法评价 时间复杂度：分配：T(n)=O(n) 收集：T(n)=O(rd) T(n)=O(d(n+rd)) 空间复杂度：S(n)=2rd个队列指针。+n个指针域空间 对于n个记录（假设每个记录含有d个关键字，每个关键字的取值范围为rd个值，进行链式基数排序的时间复杂度为O(d(n+rd))，其中每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集。 其中： n——记录数 d——关键字数 rd——关键字取值范围 * 9.6 各种内部排序方法的比较讨论 排序方法 平均时间 最坏情况 辅助存储 简单排序 O(n2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(logn) 堆排序 O(nlogn) O(nlogn) O(1) 归并排序 O(nlogn) O(nlogn) O(n) 基数排序 O(n(d+rd)) O(n(d+rd)) O(rd) * 从上表可以得出如下结论： （1）从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。 （2）上表中的“简单排序”包括除希尔排序之外的所有插入排序，起泡排序和简单选择排序，其中以直接插入排序为最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将它和其它的排序方法，诸如快速排序、归并排序等结合起来使用。 * （3）基数排序的时间复杂度也可写成O(nd)。因此，它最适合用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则也可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。 （4）从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n2)的简单排序也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。 * 1、对于给定的键值序列{12，2，16，30，8，28，4，10}分别写出直接插入排序、折半插入排序、希尔排序、直接选择排序、起泡排序的过程，并算出比较和记录移动次数。 第9章 作业 * 2、对于给定的键值序列{41，62，13，84，35，96，57，39，79，61，15，83}，分别写出快速排序、归并排序、堆排序的各趟排序结果。 3、本章介绍的内部排序方法中，哪几种是稳定的？哪几种是不稳定的？ * 一、单项选择题 1、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 （A）希尔排序 （B）冒泡排序 （C）插入排序 （D）选择排序 2、在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是 （ A）直接插入排序 （B）冒泡排序 （ C）直接选择排序 （ D）归并排序 第9章 作业 * 3、对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是 （A）简单选择排序 （B）快速排序 （C）希尔排序 （D）二路归并排序 4、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （ A）希尔排序 （B）冒泡排序 （ C）插入排序 （ D）选择排序 * 二、填空题 1、在对一组记录{54，38，96，23，15，72，60，45，83}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。 2、每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交