概念
“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假设待排序表含有n个记录,则可将其视为n个有序的子表,每个子表的长度为一,然后两两归并,得到【n/2】个长度为2或1的有序表;继续两两归并。。。如此重复,直到合并成一个长度为n的有序表为止,这种排序方法称为2路归并排序。
归并排序是使用到了分治方法(Divide and Conquer)。
算法实现
/*****************归并排序*****************/
int guibing = 10;//和总体表的大小一致
ElemType* B = (ElemType*)malloc((guibing + 1) * sizeof(ElemType));//辅助数组B
void Merge(ElemType A[],int low,int mid,int high)
{
int i, j,k;
//表A[low...mid]和A[mid+1...high]各自有序,将他们合并成一个有序表
for (int k = low; k <= mid; k++)
B[k] = A[k];
for (int i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
{
if (B[i] <= B[j])
A[k] = B[i++];//将较小值复制到A中
else
A[k] = B[j++];
}
while (i <= mid)
A[k++] = B[i++];//若第一个表未检测完,复制
while (j <= high)
A[k++] = B[j++];
}
void Merge_Sort(ElemType A[],int low,int high)
{
if (low < high)
{
int mid = (low+high)/2; //划分成两个子序列
Merge_Sort(A,low,mid);
Merge_Sort(A,mid+1,high);
Merge(A,low,mid,high); //归并
}
}