哈工大数据结构10要点.ppt

（2）建堆过程 1)?从数组中间开始调整。 2) 找出此父结点的两个子结点的较大者，再与父结点比较，若父结点小，则交换。然后以交换后的子结点作为新的父结点，重复此步骤直到没有子结点。 3)?把步骤 2)中原来的父结点的位置往前推一个位置，作为新的父结点。重复步骤 2)，直到树根为止。 88 42 75 27 6 13 80 69 88 42 6 27 75 13 80 69 13 42 6 27 75 88 80 69 69 42 6 27 75 88 80 13 69 42 6 27 75 80 88 13 建堆树的过程图 建堆过程如图所示： (3) 实现堆排序： 堆排序：将无序序列建成一个堆，得到关键字最大（或最小） 的记录；输出堆顶的最大（小）值后， 使剩余的 n-1个元素重又 建成一个堆，则可得到 n 个元素的次大（小）值；重复执行，得 到一个有序序列。 实现堆排序要解决的一个问题： 即输出堆顶元素后，怎样调整剩余的 n-1个元素，使其按关 键码成为一个新堆。 调整方法： 设有m个元素的堆，输出堆顶元素后，剩下m-1个元素。 将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满 足堆的性质。将根结点与左、右子女中较大的进行交换。 若与左子女交换，则左子树堆被破坏，且仅左子树的根结 点不满足堆的性质；若与右子女交换，则右子树堆被破坏， 且仅右子树的根结点不满足堆的性质。继续对不满足堆性 质的子树进行上述交换操作，直到叶子结点，堆被建成。 称这个自根结点到叶子结点的调整过程为筛选。 此过程的输出序列为从大到小。 其过程如图所示： 2.二分插入排序 基本思想： 直接插入算法虽然简单，但当记录数量 n 很大时，比较次数将大大增加，对于有序表（限于顺序存储结构），为了减少关键字的比较次数，可采用二分插入排序。 二分插入排序的基本思想是： 用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入。 例：若有8个记录已排序，插入新的关键字为 653 1 2 3 4 5 6 7 8 60?? 87 170 275 503 512 897 908 low=1 ① ② ③ high=8 ? m=(low+high)/2=(1+8)/2=4 （1）取关键字653，与序列中间位置①的关键字比较，653275，在后半区继续找； （2）再与后半区中间位置②的关键字比较，653512，再继续在后半区找； （3）再与后半区中间位置③的关键字比较，653897，经三次比较找到插入位置③，然后插入653。 算法： void BInsSort() { for(i=2;i=n;i++) { r[0]=r[i]; // 将r[i] 暂存到r[0] while(low=high) // 在 r[ low...high ] 中折半查找，确定所取元素在有序 序列中的大致插入位置。 当lowhigh时，循环结束，大致插入位置已确定。 { m=(low+high)/2; // 折半 if(r[0].keyr[m].key) high=m-1; // 确定新high，插入点在低半区： 即： 原low，新 high 之间 else low=m+1; // 确定新low， 插入点在高半区： 即：新low， 原 high 之间 } for(j=i-1;j=high+1;- -j) r[j+1]=r[j]; //