算法设计与分析-王红梅-第5章_减治法剖析.ppt

判定树——描述折半查找的判定过程。 长度为n的判定树的构造方法为： （1）当n=0时，判定树为空； （2）当n＞0时，判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的判定树。 具有11个结点的判定树 6 3 1 2 5 4 8 11 10 7 9 在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有n个结点的判定数的深度为 。 5.3.1 插入排序 插入排序是减治法的减一技术。 5.3 排序问题中的减治法 插入排序基本思想：依次将待排序序列中的每一个记录插入到一个已经排好序的序列中，直到全部记录都排好序 当插入第i个对象时，前面的R[1],R[2],…,R[i-1]已经排好序，此时，用R[i]的关键字与R[i-1], R[i-2],…的关键字顺序进行比较，找到插入位置即将R[i]插入，原来位置上对象向后顺移。 直接插入排序举例 i (1) (2) (3) (4) (5) (6) (0) [21] 25 49 25* 16 08 25 1 [21 25] 49 25* 16 08 49 2 [21 25 49] 25* 16 08 25* 3 [21 25 25* 49] 16 08 16 4 [16 21 25 25* 49] 08 08 5 [08 16 21 25 25* 49] 直接插入排序算法 INSERTSORT(rectype R[]) { int i,j; for (i=2;in;i++) { R[0]＝R[i]; j＝i-1; while (R[0].keyR[j].key) R[j+1]＝R[j--]; R[j+1]＝R[0]; } } 算法分析 直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。 若初始时关键字递增有序（正序），这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的移动次数为2(n-1)。 若初始时关键字递减有序（反序），这是最坏情况。这时的记录比较和移动次数分别为： 5.3.2 堆排序 以结点的编号作为下标，将堆用顺序存储结构（即数组）来存储，则堆对应于一组序列。 (a) 大根堆及其对应的序列 (b) 小根堆及其对应的序列 47 35 26 20 18 7 13 10 7 10 13 18 35 26 47 20 47 35 26 13 18 20 7 10 26 10 13 47 35 18 7 20 堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。 r1 r2 … … ri ri+1 ≤… … ≤rn-1 ≤ rn 无序区 有序区 为一个堆 已经位于最终位置 堆顶和堆中最后 一个记录交换 堆调整问题：将一个无序序列调整为堆 （1）筛选法调整堆 关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？ (a) 28与35交换 (b) 28与32交换 (c) 将28筛到叶子 28 32 18 20 12 18 20 12 35 32 18 20 12 35 35 28 32 28 假设当前要筛选结点的编号为k，堆中最后一个结点的编号为n，并且结点k的左右子树均是堆（即r[k+1]