第9章-归并排序.ppt

《第9章-归并排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章内部排序9.1排序的基本概念9.2插入类排序9.3交换类排序法9.4选择类排序法9.5归并排序9.6分配类排序9.7各种排序方法的综合比较9.8总结与提高9.5归并排序基本思想：将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1；然后两两归并，得到n/2个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。归并排序的示例为：(

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)48732651483762513478652112348765a:b:s=1s=2a:s=4b:s=8稳定的排序算法voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper2[])/*已知r1[low..mid]和r1[mid+1..high]分

3、别按关键字有序排列，将它们合并成一个有序序列，存放在r2[low..high]*/{i=low;j=mid+1;k=low;while((i<=mid)&&(j<=high)){if(r1[i].key<=r1[j].key){r2[k]=r1[i];++i;}else{r2[k]=r1[j];++j;}++k;}2路归并排序算法……..……..while(i<=mid){r2[k]=r1[i];k++;i++;}while(j<=high){r2[k]=r1[j];k++;j++;}}/*Merge*/2路归并排序算法2

4、-路归并排序可以采用递归方法实现：首先将r1[]前半段的记录用归并法排序后放到r2[]的前半段；将r1[]后半段的记录用归并法排序后放到r2[]的后半段；将r2[]的前半段和后半段合并到r3[]中。voidMergeSort(RecordTyper[],intn)/*对记录数组r[1..n]做归并排序*/{MSort(r,1,n,r);}递归算法voidMSort(RecordTyper1[],intlow,inthigh,RecordTyper3[])/*r1[low..high]经过排序后放在r3[low..high]

5、中，r2[low..high]为辅助空间*/{RecordTyper2[20];if(low==high)r3[low]=r1[low];else{mid=(low+high)/2;MSort(r1,low,mid,r2);MSort(r1,mid+1,high,r2);Merge(r2,low,mid,high,r3);}}/*MSort*/递归算法假设：前后相邻的有序段长度为h，进行两两归并后，得到长度为2h的有序段。那么一趟归并排序将调用n/2h次算法merge将r1[1…n]存放在r[1…n]中。因此时间复杂度

6、为O(n)。整个归并排序需进行m（m=log2n）趟2-路归并，所以归并排序总的时间复杂度为O（nlog2n）在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为O(n)。算法分析：类似2-路归并排序，可设计多路归并排序法，归并的思想主要用于外部排序。外部排序可分两步，①待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。②子文件多路归并，成为较长有序子文件，再记入外存，如此反复，直到整个待排序文件有序。外部排序可使用外存、磁带、磁盘，最初形成有序子文件长取决于内存所能提供排序区

7、大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。