数据结构第9章排序幻灯片.ppt

堆选择排序 例9-9 对大根堆k1={95，76，66，50，36，12，25，36}排序过程如图9.13 ： 95 76 66 36 12 25 50 36 36 76 66 36 12 25 50 95 50 76 36 25 50 66 36 12 76 36 95 25 66 12 25 36 66 76 36 95 50 36 50 12 堆选择排序 36 25 50 66 76 12 95 36 12 25 50 66 76 36 95 36 36 12 25 36 50 66 76 36 95 12 12 36 50 66 76 36 95 25 结果：k1={ 12，25，36，36，50，66，76，95 } 堆选择排序 将新换上来的根所在的二叉树调整成堆时，根结点的左右子树已满足堆定义，此时要设计一个自堆顶到叶结点的调整二叉树为堆的算法，称之为“筛选”算法，它是堆排序的一个关键算法，堆排序的大部分工作依赖于筛选算法。 ①筛选算法思路：设要调整成堆的完全二叉树如图9.14 ： 其中s为当前根的序号。先将R[s]?temp，令j=s结点的左右孩子key最大者的序号。将temp.key与kj比较，若kjtemp.key，则R[j] ? R[s]。然后令s=j，j等于新s的左右孩子key最大者的序号，继续temp.key与kj的比较……，直到某个kj≤temp.key或已调整到叶子层时，将temp送入最后一个s位置处，筛选算法结束。 R[s] R[2s] R[2s+1] R[n] temp j s j 或 ②筛选算法描述 void Adjust (sqfile F, int s, int n) ∥将（F.R[s]……F.R[n]）调整成大根堆∥ { Retype temp; int j; temp=F.R[s]; ∥暂存F.R[s]∥ j=2*s; ∥令j为s结点的左子序号∥ while (j=n) { if (jnF.R[j+1].keyF.R[j].key) j++; ∥令j为s的左右孩子key最大者的序号∥ if (F.R[j].keytemp.key) { F.R[s]=F.R[j]; ∥R[j] ? R[s]∥ s=j; j=2*s; ∥置新的调整点∥ } else break; ∥调整完毕，退出循环∥ } F.R[s]=temp; ∥最初的根回归∥ } 堆选择排序 再讨论第(1)步，将F=（R1 R2……Rn）建成堆。方法是将F看作是一棵完全二叉树，从最后一个有孩子的结点起，反复调用筛选算法，逆序向根逐步将F调整成堆。 例9-10 设排序前文件的关键字集合k={50，36，66，76，95，12，25，36}，n=8。根据二叉树性质5，n号结点的父结点序号为n/2=4，即从第4号结点起，逆序（4，3，2，1）到根，调用筛选算法，逐步求堆。过程如图9.15： 50 36 66 95 12 25 76 36 1 2 3 4 5 6 7 8 95 36 95 50 50 76 3.堆排序算法 void Heapsort (sqfile F) ∥对顺文件F的堆排序算法∥ { int i; Retype temp; for (i=F.len/2;i=1;i--) Adjust (F,i,F.len); ∥调整（R[i]……R[n]）为堆∥ for (i=F.len;i=2;i--) ∥选择n－1次∥ { temp=F.R[1]; ∥根与当前最后一个结点互换∥ F.R[1]=F.R[i]; F.R[i]=temp; Adjust (F ,1,i-1); ∥互换后再建堆∥ } } 4.算法分析 设待排文件长度为n，相应n个结点的完全二叉树如图9.16： 算法分析 根据第六章二叉树性质4，n个结点的完全二叉树的深度： 对筛选算法Adjust( )：若从根向下调整完全二叉树为堆，key比较次数最多为2(k－1)（while循环里有2次key比较），则有： 1 2 3 n 层号 1 2 3 k-1 k 算法分析 堆排序算法Heapsort( )： 第一个for循环中，每个有孩子结点的子树都要调用一次筛选算法Adjust( )，如表9.1：