数据结构课件--第九章.pptVIP

堆排序 堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆 算法评价 时间复杂度： 分配：T(n)=O(n) 收集：T(n)=O(rd) T(n)=O(d(n+rd)) 其中：n——记录数 d——关键字数 rd——关键字取值范围 空间复杂度：S(n)=2rd个队列指针+n个指针域空间 例 含8个元素的无序序列（49，38，65，97，76，13，27，50） 49 65 38 27 13 76 97 50 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97 问题3:如何利用堆进行排序？ 进行堆排序的步骤：①将待排序记录按照堆的定义建初堆（算法9.10），并输出堆顶元素；②调整剩余的记录序列，利用筛选法将前n-i个元素重新筛选建成为一个新堆，再输出堆顶元素；③重复执行步骤②n-1次进行筛选, 新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多，最后使待排序记录序列成为一个有序的序列，这个过程称之为堆排序。 完整的堆排序过程见p246的图9.10,图中箭头所指为当前堆尾结点。 返回主目录 堆排序的算法为： void HeapSort（RecordType r[],int length） /* 对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */ { crt_heap（ r, length）；n= length; for ( i=n ; i= 2 ; --i) { b=r[1]; /* 将堆顶记录和堆中的最后一个记录互换 */ r[1]= r[i] r[i]=b; sift(r，1，i-1) ； /* 进行调整，使r[1..i-1]变成堆 */ } } /* HeapSort */ 返回主目录 堆排序算法分析： 堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。对深度为k的堆，筛选算法中进行的关键字的比较次数至多为2（k-1）次，则在建含n个元素、深度为h的堆时，总共进行的关键字比较次数不超过4n。另外，n个结点的完全二叉树的深度为：?log2n? +1，则调整建新堆时调用sift过程n-1次总共进行的比较次数不超过： 2(?log2(n-1)? + ?log2(n-2)? +…+ ?log22? 2n ?log2n? 因此，堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。 堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。 返回主目录 9.5 归并排序 基本思想是将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到?n/2?个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。 返回主目录 归并排序的示例为： (19) (13) (05) (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) (01,05,13,16,19,26,27,31) 返回主目录 2-路归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列。 合并算法描述如下： void Merge ( RecordType r1[], int low, int mid, int high, RecordType r[]) /*已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r[low..high] */ {i=low；j=mid+1； k=low； while ( (i=mid)(j=high) ) {if ( r1[i].key=r1[j].key ) {r[k]=r1[i]