归并排序思路 排序 - 归并排序（一）

排序 - 归并排序（一）  

　　归并排序(Merge Sort)是利用 归并 技术来进行排序 归并是指将若干个已排序的子文件合并成一个有序的文件

　　两路归并算法

　　 算法基本思路

　　设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上 R[low m] R[m+ high] 先将它们合并到一个局部的暂

　　存向量R (相当于输出堆)中 待合并完成后将R 复制回R[low high]中

　　( )合并过程

　　合并过程中 设置i j和p三个指针 其初值分别指向这三个记录区的起始位置 合并时依次比较R[i]和R[j]的关键字 取关键

　　字较小的记录复制到R [p]中 然后将被复制记录的指针i或j加 以及指向复制位置的指针p加

　　重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空) 此时将另一非空的子文件中剩余记录依次复制到

　　R 中即可

　　( )动态申请R

　　实现时 R 是动态申请的 因为申请的空间可能很大 故须加入申请空间是否成功的处理

　　 归并算法

　　void Merge(SeqList R int low int m int high)

　　{//将两个有序的子文件R[low m)和R[m+ high]归并成一个有序的

　　//子文件R[low high]

　　int i=low j=m+ p= ; //置初始值

　　RecType *R ; //R 是局部向量 若p定义为此类型指针速度更快

　　R =(ReeType *)malloc((high low+ )*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[low high]