|
归并排序 归并排序有两种实现方法自底向上和自顶向下 自底向上的方法 () 自底向上的基本思想 自底向上的基本思想是第趟归并排序时将待排序的文件R[n]看作是n个长度为的有序子文件将这些子文件两两归并若 n为偶数则得到 个长度为的有序子文件;若n为奇数则最后一个子文件轮空(不 参与归并)故本趟归并完成后前 个有序子文件长度为但最 后一个子文件长度仍为;第趟归并则是将第趟归并所得到的 个有 序的子文件两两归并如此反复直到最后得到一个长度为n的有序文件为止 上述的每次归并操作均是将两个有序的子文件合并成一个有序的子文件故称其为二路归并排序类似地有k(k>)路归并排序 () 二路归并排序的全过程 【 参见动画演示 】 () 一趟归并算法 分析 在某趟归并中设各子文件长度为length(最后一个子文件的长度可能小于length)则归并前R[n]中共有 个有序的 子文件R [length]R[length+length]… 注意 调用归并操作将相邻的一对子文件进行归并时必须对子文件的个数可能是奇数以及最后一个子文件的长度小于length这两种特殊 情况进行特殊处理 ① 若子文件个数为奇数则最后一个子文件无须和其它子文件归并(即本趟轮空); ② 若子文件个数为偶数则要注意最后一对子文件中后一子文件的区间上界是n 具体算法如下 void MergePass(SeqList Rint length) { //对R[n]做一趟归并排序 int i; for(i=;i+*length<=n;i=i+*length) Merge(Rii+lengthi+*length); //归并长度为length的两个相邻子文件 if(i+length Merge(R，i，i+length-1，n); //归并最后两个子文件 //注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并 } //MergePass (4)二路归并排序算法 void MergeSort(SeqList R) {//采用自底向上的方法，对R[1..n]进行二路归并排序 int length; for(1ength=1;length 趟归并 MergePass(R，length); //有序段长度≥n时终止 } 注意： 自底向上的归并排序算法虽然效率较高，但可读性较差。tW.WiNgWit.cOM |
