|
归并排序(Merge Sort)是利用归并技术来进行排序归并是指将若干个已排序的子文件合并成一个有序的文件 两路归并算法 算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上R[lowm]R[m+high]先将它们合并到一个局部的暂 存向量R(相当于输出堆)中待合并完成后将R复制回R[lowhigh]中 ()合并过程 合并过程中设置ij和p三个指针其初值分别指向这三个记录区的起始位置合并时依次比较R[i]和R[j]的关键字取关键 字较小的记录复制到R[p]中然后将被复制记录的指针i或j加以及指向复制位置的指针p加 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)此时将另一非空的子文件中剩余记录依次复制到 R中即可 ()动态申请R 实现时R是动态申请的因为申请的空间可能很大故须加入申请空间是否成功的处理 归并算法 void Merge(SeqList Rint lowint mint high) {//将两个有序的子文件R[lowm)和R[m+high]归并成一个有序的 //子文件R[lowhigh] int i=lowj=m+p=; //置初始值 RecType *R; //R是局部向量若p定义为此类型指针速度更快 R=(ReeType *)malloc((highlow+)*sizeof(RecType)); if(! R) //申请空间失败 Error(Insufficient memory available!); while(i<=m&&j<=high) //两子文件非空时取其小者输出到R[p]上 R[p++]=(R[i]key<=R[j]key)?R[i++]R[j++]; while(i<=m) //若第个子文件非空则复制剩余记录到R中 R[p++]=R[i++]; while(j<=high) //若第个子文件非空则复制剩余记录到R中 R[p++]=R[j++]; for(p=i=low;i<=high;p++i++) R[i]=R[p];//归并完成后将结果复制回R[lowhigh] } //Merge |
