第8单元 内部排序.pptVIP

8.4.2 堆排序 3.性能分析 (1)时间性能分析 堆排序的主要时间耗费在建初始堆和调整堆上。对n个记录的待排序列建立深度为k的堆，已知 ，则： 建初始堆，总共进行的关键字比较不超过4n次，所以建堆的时间复杂度为O(n)。 在筛选算法中，从根到叶子的筛选，关键码比较次数至多为2(k-1)次，交换记录至多k次。调整、建新堆时调用heapadjust过程n-1次，因此，总的比较次数不超过： 所以，堆排序的总时间代价为O(n)+O(nlog2n)= O(nlog2n)。理论上，堆排序最好、最差、平均情况下的时间复杂度为O(nlog2n)。 8.4.2 堆排序 3.性能分析 (2)空间性能分析 堆排序仅在交换堆顶元素和堆底元素时使用了一个临时单元r[0]，其空间复杂度S(n)=O(1)。 (3)稳定性 在调整过程中，完全二叉树的父子结点之间的移动不能保证两个关键码相同的记录一定保持原始输入顺序。例如图9.8中，算法的执行改变了65和65’的原始顺序。 8.5 归并排序 归并排序是利用“归并”技术来进行排序，所谓“归并”是指将若干个已排序的子序列合并成一个有序序列。归并排序通常分为2-路归并和多路归并，2-路归并一般用于内部排序，多路归并一般用在外部磁盘数据排序中。本节主要介绍2-路归并排序。 8.5归并排序 1.基本思路 2-路归并排序的过程很简单，首先是将原始序列划分成两个子序列，再分别对这两个子序列进行归并排序。因此，2-路归并排序是一个递归的过程，它主要包含两个操作：划分序列和将两个有序表合并为一个有序表。 2-路归并排序除了递归描述外，还可以采用迭代的描述方式，基本思路如下：首先将初始序列中的n个记录看成n个有序的子序列，每个子序列长度为1；两两合并，得到?n/2?个长度为2或1的有序子序列；再两两合并，……，如此重复，直至得到一个长度为n的有序序列。 8.5归并排序 1.基本思路 2-路归并排序的过程很简单，首先是将原始序列划分成两个子序列，再分别对这两个子序列进行归并排序。因此，2-路归并排序是一个递归的过程，它主要包含两个操作：划分序列和将两个有序表合并为一个有序表。 2-路归并排序除了递归描述外，还可以采用迭代的描述方式，基本思路如下：首先将初始序列中的n个记录看成n个有序的子序列，每个子序列长度为1；两两合并，得到?n/2?个长度为2或1的有序子序列；再两两合并，……，如此重复，直至得到一个长度为n的有序序列。 8.5归并排序 2.归并排序算法 2-路归并排序不论采用递归方式还是迭代方式实现，排序中的基本操作都是将两个有序表合并成一个有序表。 设r[s..t]由两个有序子表r[s..m] 和r[m+1..t]组成，两个有序子表合并成一个有序表r1[s..t]。该算法在第2章中详细介绍，具体如下： 8.5归并排序 2.归并排序算法 void merge( Rectype r[],Rectype r1[],int s,int m,int t) { i=s;j=m+1;k=s; while(i=mj=t) if(r[i].keyr[j].key) r1[k++]=r[i++]; else r1[k++]=r[j++]; while(i=m) r1[k++]=r[i++]; while(j=t) r1[k++]=r[j++]; } 8.5归并排序 2.归并排序算法 (1) 2-路归并排序递归算法 void msort(Rectype r[],Rectype r1[],int s,int t) /*将r[s..t]归并排序为r1[s..t]*/ { int m; if(s==t) r1[s]=r[s]; else { m=(s+t)/2; /*将r分成两部分*/ msort(r,r1,s,m); /*递归地将r[s..m]归并为有序的r1[s..m]*/ msort(r,r1,m+1,t); /*递归地将r[m+1..t]归并为有序的r1[m+1..t]*/ merge(r1,r,s,m,t); /*将r1[s..m]和r1[m+1..t]合并为r1[s..t]*/ } } void binarymergesort(Rectype r[],int n) /*对序列r[1..n]归并排序为r1[1..n]*/ { msort(r,1,n); } 8.5归并排序 2.归并排序算法 (2) 2-路归并排序迭代算法