第8章数据结构排序技术案例.ppt

设关键码分别为k1, k2, …, km，多键排序有两种方法： ⑴ 依次对记录进行m次排序，第一次按k1排序，第二次按k2排序，依此类推。这种方法要求各趟排序所用的算法是稳定的； ⑵ 将关键码k1, k2, …, km分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。 排序的分类 1. 基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为Ω（nlog2n）。 2. 不基于比较：根据关键码的分布特征。 直接插入排序过程示例 希尔插入排序过程示例 起泡排序过程示例 算法描述： index=i; for (j=i+1; j=n; j++) if (r[j]r[index]) index=j; 解决方法： 设置一个整型变量index，用于记录在一趟比较的过程中关键码最小的记录位置。 关键问题⑴：如何在无序区中选出关键码最小的记录？ 解决方法： 第i趟简单选择排序的待排序区间是r[i] ~ r[n]，则r[i]是无序区第一个记录，所以，将index所记载的关键码最小的记录与r[i]交换。 选择排序 关键问题⑵：如何确定最小记录的最终位置？ 算法描述： if (index!=i) r[i]←→r[index]; void selectSort ( int r[ ], int n) { for ( i=1; in; i++) { index=i; for (j=i+1; j=n; j++) if (r[j]r[index]) index=j; if (index!=i) r[i]==r[index]; } } 简单选择排序算法 选择排序 简单选择排序算法的性能分析 移动次数： 最好情况（正序）：0次 选择排序 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 最坏情况：3(n-1)次 简单选择排序算法的性能分析 移动次数： 最好情况（正序）：0次 选择排序 空间性能：需一个辅助空间。 稳定性：是一种稳定的排序算法。 4 5 2 3 1 1 5 2 3 4 1 2 5 3 4 1 2 3 5 4 1 2 3 4 5 1 2 3 4 比较次数： ) ( ) 1 ( 2 1 2 1 1 n O n n i n n i = - = - ? - = ） （ 简单选择排序的时间复杂度为O(n2)。 堆排序 改进的着眼点：如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。 选择排序 减少关键码间的比较次数 查找最小值的同时，找出较小值 堆的定义 堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。 选择排序 18 20 32 36 45 25 38 50 40 28 1. 小根堆的根结点是所有结点的最小者。 2. 较小结点靠近根结点，但不绝对。 堆的定义 堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。 选择排序 50 38 45 40 28 36 32 20 18 28 1. 大根堆的根结点是所有结点的最大者。 2. 较大结点靠近根结点，但不绝对。 堆和序列的关系 选择排序 将堆用顺序存储结构来存储，则堆对应一组序列。 50 38 45 40 28 36 32 20 18 28 50 38 45 32 36 40 28 20 18 28 1 2 3 4 5 6 7 8 9 10 采用顺序存储 基本思想：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。 选择排序 堆排序 需解决的关键问题? ⑴如何由一个无序序列建成一个堆（即初始建堆）？ ⑵如何处理堆顶记录？ ⑶如何调整剩余记录，成为一个新堆（即重建堆）？ 堆调整 堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？ 选择排序 28 36 32 16 18 25 32 1