【算法】归并算法

归并排序理解

”归并“含义:将两个或两个以上的有序表组合成一个新的有序表。

假定待排序表含有n个记录，可将其视为n个有序表的子表，每个子表长度为1.然后两两归并，得到[n/2]个长度为2或1的有序表；继续两两归并...重复操作，知道合并为一个长度为n的有序表为止，这种排序算法称作2路归并排序

2路归并算法示例

merge()功能是将前后相邻的两个有序表归并为一个有序表。

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));//辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
    //表A的两端A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
    for(int k=low;k<=high;k++){
        B[k]=A[k];//将A中所有元素复制到B
    }
    for(i=low;j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])    //比较B左右两端中的元素
            A[k]=B[i++];  //较小的复制到A中
        else
            A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];//若第一个表未检测完，复制
    while(j<=high) A[++]=B[j++];//若第二个表未检测完，复制
}

上面代码中，最后两个while只有一个循环会执行。

上述算法原理：设两端有序表为A[low...mid]、B[mid...high]存放在同一顺序表的相邻位置，先将他们复制到辅助数组B。每次从对应的B中的两段取出一个记录进行关键字比较，将较小的放进A，当数组B有一段的下标超出其对应的表长（即所有元素已全部复制到A中），讲另一端中的剩余布冯直接复制A中。

递归形式的2路算法是基于分治的，过程如下：

分解：将含有n个元素的待排序表分成各含n/2各元素的子表，采用2路归并排序算法对两个子表递归进行排序。

合并：合并两个已排序的子表得到排序结果

void MergeSort(ElemType A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;//从中间分开成为两个子序列
        MergeSort(A,low,mid);//对左侧子序列进行递归排序
        MergeSort(A,mid+1,high);//对右侧序列进行递归排序
        Merge(A,low,mid,high);//归并
    }
}

性能分析：

空间效率：Merge()操作中，辅助空间刚好为n各单元，所以算法的空复杂度为O(n)。

时间效率：每趟归并的时间复杂度为O(n),一共需要进行[log2n]趟归并，所复杂度是O(nlog2n).

稳定性：由于Merge()操作不会改变相同关节子记录的相对次序，所以2路归并算法是一种稳定的排序算法。