所谓“归并”，是将两个或两个以上的有序文件合并成为一个新的有序文件。归并排序的一种实现方法是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到[
n
2
frac n2
2n]个长度为2或1的有序文件，再两两归并，如此重复，直到最后形成包含 n 个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
两路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
【算法】将分别有序的 data[s…m]和 data[m+1…n]归并为有序的data[s…n]。
void Merge(int data[], int s, int m, int n)
{
int i, start = s, k = 0;
int *temp;
temp =(int *)malloc((n-s+1)*sizeof(int)); /*辅助空间*/
for(i= m+1; s <= m &&i<= n; ++k) /*将 data[s..m]与data[m+l..n]归并后存入temp*/
if (data[s] < data[i]) temp[k] = data[s++];
else temp[k] = data[i++];
for(; s <= m; ++k) /*将剩余的data[s..m]复制到 temp*/
temp[k] = data[s++];
for(; i <= n; ++k) /*将剩余的data[i..n]复制到 temp*/
temp[k] = data[i++];
for(i=0; i<k; i++)
data[start++] = temp[i]:
free(temp);
}/*Merge*/
一趟归并排序的操作是：调用[n/2h]次 Merge 算法，将数组 data1[0…n-1]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为 2h 的有序段，并存放在 data2[0…n-1]中，整个归并排序需进行[log2n]趟。归并排序需要辅助空间n个(与待排记录数量相等)，时间复杂度为O(nlogn)。
【算法】递归形式的两路归并。
void MSort(int data[], int s, int t) /*对 data[s..t]进行归并排序*/
{
int m;
if(s<t){
m = (s+t)/2; /*将 data[s..t]均分为 data[s..m]和 data[m+1..t]*/
MSort(data, s, m); /*递归地对 data[s..m]进行归并排序*/
MSort(data, m+1, t); /*递归地对 data[m+1..t]进行归并排序*/
Merge(data, s, m, t); /*将 data[s..m]和 data[m+1..t]归并为data[s..t]*/
}
}/*MSort*/
【算法】对一维数组 data[0…n-1]中的元素进行两路归并排序。
void MergeSort(int data[], int n)
{
MSort(data, 0, n-1);
}/*MergeSort*/
原文地址:https://blog.csdn.net/qq_33501207/article/details/136067107
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_67687.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
