[文学]数据结构教程 第九章 排序.ppt

9.4 选择排序 9.4.3 堆排序 1. 基本思想 (1)把用数组来存储待排序的数据转换成一棵完全二叉树。 (2)将完全二叉树转换成堆树。 (3)有了堆树后，便开始排序。 下一页 上一页 9.4 选择排序 9.4.3 堆排序 2.【例9-8】输入数据序列为:80 13 6 88 27 75 42 69，分析其堆排序的过程。 (1)位置(i) 对于任一位置，若父结点的位置为i，则它的两个子结点分别位于2i和2i+1。所以根据数组中的数据画出如图9-8所示的完全二叉树。 下一页 上一页 9.4 选择排序 9.4.3 堆排序 (2)建堆过程 ①从数组中间开始调整。 ②找出此父结点的两个子结点的较大者，再与父结点比较，若父结点小，则交换。然后以交换后的子结点作为新的父结点，重复此步骤直到没有子结点。 ③把步骤②中原来的父结点的位置往前推一个位置，作为新的父结点。重复步骤(2)，直到树根为止。 整个过程如图9-9所示。 下一页 上一页 9.4 选择排序 9.4.3 堆排序 (3)实现堆排序 实现堆排序要解决的一个问题:即输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。 调整方法:设有m个元素的堆，输出堆顶元素后，剩下m-1个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。将根结点与左、右子女中较大的进行交换。若与左子女交换，则左子树堆被破坏，且仅左子树的根结点不满足堆的性质;若与右子女交换，则右子树堆被破坏，且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。称这个自根结点到叶子结点的调整过程为筛选。其过程如图9-10所示。 下一页 上一页 9.4 选择排序 9.4.3 堆排序 3.算法 void HeapAdjust(S TBL *h,int s,int m) { //a[s...m]中的记录关键码除a[s]外均满足堆的定义，本函数 将对第s个节点为根的子树筛选，使其成为大顶堆 ac=h-a[s]; for(j=2*s;j=m;j=j*2)//沿关键码较大的子女结点向下筛选 { if(jmh-a[j].keyh-a[j+1].key) j=j+1; //为关键码较大的元素下标 if(ac.keyh-a[j].key) break;//ac应插入在位置s上 h-a[s]=h-a[j];s=j; } h-a[s]=ac;//插入 } 下一页 上一页 9.4 选择排序 9.4.3 堆排序 3.算法 void HeapSort(S TBL *h) { for(i=h-length/2;i0;i--)//将a[1...length]建成堆 HeapAdjust(h,i,h-length); for(i=h-length;i1;i--) { h-a[1]--h-a[j];//堆顶与堆底元素交换 HeapAdjust(h,1,i-1);//将a[1...i-1]重新调整为堆 } } 下一页 上一页 9.4 选择排序 9.4.3 堆排序 4.效率分析 设树高为k，k=|(log2(n))|+1。从根到叶的筛选，关键字比较次数至多2(k-1)次，交换记录至多k次。所以，在建好堆后，排序过程中的筛选次数不超过下式 2(|log2(n-1)|+|log2(n-2)|+…+|log22|2 nlog2n 而建堆时的比较次数不超过4n次，因此堆排序最坏情况下，时间复杂度也为0(nlog2n) 上一页 返 回 9.5 归并排序 1.基本思想 (1)将n个记录的待排序序列看成是有n个长度都为1的有序子表组成。 (2)将两两相邻的子表归并为一个有序子表。 (3)重复上述步骤，直至归并为一个长度为n的有序表。 2.【例9-9】设初始关键字序列为:49 38 65 97 76 13 27 20执行归并排序的过程如图9-11所示 下一页 9.5 归并排序 3. 算法 void Merge(int low,int mm,int high) //两个相邻有序段的合并 { int i=low,j=mm+1;p=0; RecType *R1; while(i=mmj=high) R1[p++]=(R[i].key=R[j].key)?R[i++]:R[j++]; while(i=mm) R1[p++]=R[i++]; while(j=hig