第8章 排序研究.ppt

008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集 设置10个队列，f[i]和e[i]分别头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列 链式基数排序步骤 重复执行d趟“分配”与“收集” 每趟对 n 个记录进行“分配”，对rd个队列进行“收集” 需要增加n+2rd个附加链接指针。 n个记录 每个记录有 d 位关键字 关键字取值范围rd(如十进制为10) 算法分析 时间效率：O(d( n+rd)) 空间效率：O(n+rd) 稳 定 性：稳定 小结 1. 熟练掌握直接插入排序、折半插入排序、冒泡排序、快速排序、直接选择排序的算法实现及其性能分析 2. 掌握希尔排序、归并排序、堆排序的方法及其性能分析 3.各种内部排序方法的比较（时间、空间、稳定性、选择原则） 4.堆的概念、判别方法、存储结构 5. 掌握外部排序方法中败者树的建立及归并方法，掌握置换-选择排序的过程和最佳归并树的构造方法 北京林业大学信息学院 （数据不是顺次后移时将导致方法不稳定） 排序算法比较 按平均时间排序方法分为四类 O(n2)、O(nlogn)、O(n1+?)、O(n) 知道各级关键字的主次关系 知道各级关键字的取值范围 快速排序是基于比较的内部排序中平均性能最好的 基数排序时间复杂度最低，但对关键字结构有要求 排序算法比较 为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构 　　　直接插入排序、归并排序、基数排序 不宜采用链表作为存储结构的 　　　折半插入排序、希尔排序、快速排序、堆排序 排序算法比较 （1）分布随机，稳定性不做要求，则采用快速排序 （2）内存允许，要求排序稳定时，则采用归并排序 （3）可能会出现正序或逆序，稳定性不做要求，则采用堆排序或归并排序 排序算法选择规则 n较大时 （1）基本有序，则采用直接插入排序 （2）分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排序 n较小时 堆的重新调整－5 10 30 4 8 60 10 7 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 3 6 2 8 5 8 1 8 10 8 30 8 60 10 70 70 60 60 40 40 30 30 12 12 堆的重新调整－5 10 30 4 8 60 10 7 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 3 6 2 8 5 8 1 8 10 8 30 8 60 10 70 70 60 60 40 40 30 30 12 12 堆的重新调整－5 8 30 4 8 60 10 7 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 3 6 2 8 5 10 1 10 8 8 30 8 60 10 70 70 60 60 40 40 30 30 12 12 堆的重新调整－6 8 30 4 8 60 10 7 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 3 6 2 8 5 10 1 10 8 8 30 8 60 10 70 70 60 60 40 40 30 30 12 12 堆的重新调整－6 8 30 4 8 60 10 7 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [