《数据结构-C语言描述》课件第9章.ppt

图9.10完整的堆排序过程堆排序的算法如下：voidHeapSort（RecordTyper［］,intlength）/*对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*/【算法9.11堆排序算法】堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。对深度为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较大的文件还是很有效的。对于层次为k=［log2n］+1的堆，筛选过程最多执行k次，建堆的时间复杂度为O(log2n)。对于有n个结点的堆(2k-1n≤2k)，第k层最多有2k-1个记录参加比较，在第i(1≤i≤k-1)层，有2i-1个记录参加比较，则需要检查以它为根的子树是否为堆，每个元素的最大调整次数为记录在树中的层次（k-i），因此重建堆共需要的调整次数为 ，n个结点调用重建堆的过程n-1次，堆排序的时间复杂度为O(nlog2n)。9.5归并排序前面介绍的三类排序方法：插入排序、交换排序和选择排序，都是将一组记录按关键字大小排成一个有序的序列。而本节介绍的归并排序法，它的基本思想是将两个或两个以上的有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到［n/2］个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称做2路归并排序。图9.11为一个2路归并示例。图9.11归并排序示例2路归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列。合并算法描述如下：voidMerge(RecordTyper1［］,intlow,intmid,inthigh,RecordTyper［］)/*已知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］；++i；}else{r［k］=r1［j］；++j；}++k；}while(i≤mid){r［k］=r1［i］;k++;i++;}while(j≤high){r［k］=r1［j］;k++;j++;}}/*Merge*/ 【算法9.122路归并算法】在合并过程中，两个有序的子表被遍历了一遍，表中的每一项均被复制了一次。因此，合并的代价与两个有序子表的长度之和成正比，该算法的时间复杂度为O(n)。2路归并排序可以采用递归方法实现，具体描述如下：voidMergeSort(RecordTyper1［］,intlow,