归并排序(MergeSort)(防止标题重复)-蒲公英云

归并排序(MergeSort)(防止标题重复)

归并排序(MergeSort)
1 归并排序原理
分解成最小的记录块(长度为0或1),必须要排序,就是有序块
然后再归并
2 归并排序算法的实现

//归并的实现
//有序子序列R[low...mid]与R[mid + 1...high]归并到S[low...high]
void Merge(Rcd R[], int low, int mid, int high, Rcd &S[])
{
    P_left = low;
    P_right = mid + 1;
    P_result = low;
    while (P_left <= mid && P_right <= high)
    {
        if (R[P_left] <R[P_right])
        {
            S[P_result] = R[P_left];
            P_result++;
            P_left++;
        }
        else 
        {
            S[P_result] = R[P_right];
            P_result++;
            P_right++;
        }
    }
    while (P_left <= mid)
    {
        S[P_result] = R[P_left];
        P_result++;
        P_left++;
    }
    while (P_right <= high)
    {
        S[P_result] = R[P_right];
        P_result++;
        P_right++;
    }
}
//归并排序的对外封装
void MergeSort(Rcd R[], int low, int high, Rcd &T[])
{
    //只有一个结点的序列
    if (low == high) T[low] = R[low];
    else 
    {
        mid = (low + high)/2;
        MergeSort(R, low, mid, S);
        MergeSort(R, mid + 1, high, S);
        Merge(S, low, mid, high, T);
    }
}