数据结构与算法分析设计课件.ppt

Shell排序算法在各小组内采用直接插入排序时，其平均比较次数和平均移动次数都为O(n1.3)左右。 Shell排序算法中增加了一个辅助空间temp，因此算法的辅助空间为S(n)=O(1)。 Shell排序是不稳定的。 代价分析 8.3 选择排序 基本方法是∶每步从待排序记录中选出排序码最小的记录，放在已排序的记录序列的后面，直到全部排完。 直接选择排序 堆排序。 8.3.1 直接选择排序 首先在所有记录中选出排序码最小的记录，与第一个记录交换，然后在其余的记录中再选出排序码最小的记录与第二个记录交换，以此类推，直到所有记录排好序。 例：初始序列为 49，38，65，97，49’，13，27，76，请用直接选择排序法排序。 排序过程如图8.5所示。其中第i步选择出的最小元素与第i个元素间用线联结，被方括号括起来的部分是已经排序的部分。 直接选择排序采用顺序存储方式，存储结构的定义同SortObject。 直接选择排序的程序实现： void selectSort(SortObject * pvector) 存储结构与算法的实现 通过对于字典的二叉排序树表示的讨论发现：同样的字典可以有许多不同的二叉排序树表示，其中检索平均比较次数最小的二叉排序树称作最佳二叉排序树。 在所有结点检索的概率都相等的情况，只要先将结点按关键码排序，然后按二分法依次检索关键码，从空二叉排序树开始，将检索中遇到的还未在二叉排序树中的结点插入。最后得到的就是这个字典的一个最佳二叉排序树。 构造不等概情况的最佳二叉排序树不像等概情况那么直观，但是根据最佳二叉排序树的每个子树也是最佳二叉排序树的特点，可以从小到大地采用动态规划方法构造它。 最佳二叉排序树主要适合表示静态字典，对于动态字典需要能够动态地调整二叉排序树平衡的AVL树表示。AVL树每个结点的左、右子树高度之差的绝对值不超过1。 在平衡二叉排序树中插入新结点时，如果新结点插入后破坏了二叉排序树的平衡，需要找出最小不平衡子树，在保证排序性质的前提下，调整最小不平衡子树中各结点的连接关系，以达到新的平衡。 文件是大型字典在外存上的表示。对于大型的文件的索引也是一种文件。本章重点讨论如何分层次组织索引的结构，使得索引顺序文件的检索取得比较高的时间效率。 多分树是一种树形、静态、多级索引结构。多分树的叶结点就是主文件的最底层索引。主文件的每个页块可以看成是多分树的外部结点。 B树是一种树形、多级、动态索引结构，B+树可以看作是B树的改进。对于相同大小的结点空间，B+树可以设计的阶数比B树大。因此，B+树可以比B树更快地实现检索。 第八章 排序 目录 8.1 基本概念 8.2 插入排序 8.2.1 直接插入排序 8.2.2 二分法插入排序 8.2.3 表插入排序 8.2.4 Shell排序 8.3 选择排序 8.3.1 直接选择排序 8.3.2 堆排序 ? 8.4 交换排序 8.4.1 起泡排序 8.4.2 快速排序 8.5 分配排序 8.5.1 概述 8.5.2 基数排序 8.6 归并排序 8.6.1 内排序 8.6.2 外排序* 8.1 基本概念 排序的对象是由一组记录组成的文件，每个记录由若干字段组成，所谓排序码是记录中的一个(或多个)字段，排序以排序码为依据。 排序码可以不是关键码，则可能有多个记录具有相同的排序码，使得排序的结果不唯一。 排序码之间需要进行比较，本章中都假设排序码为整型。 设{R0,R1,…,Rn-1}是由n个记录组成的文件，{K0,K1,…,Kn-1}是排序码集合，所谓排序就是将文件中的全部记录按排序码不增(或不减)的次序重新排列。 排序看成字典上的操作 在排序的讨论中，并不关心被排序对象本身的逻辑结构，所以读者可以把排序看成是字典上的一种操作。 不同的排序算法，可能依赖与不同的存储结构，可以理解为在字典的不同存储表示上排序的实现。 而把非字典结构中元素的排序，归结为是对于其结点按照排序码建立的密集索引的排序。 与上一章关于索引的讨论类似，在本章的具体排序算法中，只关心排序码的作用和表示，而把记录中的其它字典隐藏起来。  在待排序的文件中，如果存在多个排序码相同的记录，经过排序后，相同排序码记录的相对次序如果保持不变，则称这种排序方法是稳定的，否则是不稳定的。 稳定性 本章中提到的记录和文件，主要是指内存的数据。待排序的记录在排序过程中全部存放在内存的称为内排序，否则称为外排序。外排序也就是外存文件的排序。 本章讨论的主要是内排序的方法，但有些方法(例如归并排序)也适用于外排序。 内排序与外排序 排序方法分类 插入排序、 选择排序、 交换排序、 分配排序、 归并排序。 （每一种方法具体可能有多个不同算法） 评价排