掌握算法-排序-归并排序

欢迎大家来到IT世界,在知识的湖畔探索吧!

这个算法中基本的操作是合并两个已排序的表。因为这两个表是已排序的，所以若将输出放到第三个表中时则该算法可以通过对输入数据来一趟排序来完成。

基本的合并算法是取两个输入数组A和B，一个输出数组C，以及三个计数器Aptr, Bptr, Cptr，它们初始置于对应数组的开始端。A[Aptr]和B[Bptr]中的较小者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完的时候，则将另一个表中的剩余部分拷贝到C中。

#include <iostream>
typedef int ElementType; 

void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)
{
    int LeftEnd = Rpos -1;
    int TmpPos = Lpos;
    int NumELements = RightEnd - Lpos + 1;

    while(Lpos <= LeftEnd && Rpos <= RightEnd){
        if(A[Lpos] <= A[Rpos]){
            TmpArray[TmpPos++] = A[Lpos++];
        }
        else{
            TmpArray[TmpPos++] = A[Rpos++];
        }
    }

    while(Lpos <= LeftEnd){
        TmpArray[TmpPos++] = A[Lpos++];
    }

    while(Rpos <= RightEnd){
        TmpArray[TmpPos++] = A[Rpos++];
    }

    for (int i = 0; i < NumELements; i++, RightEnd--){
        A[RightEnd] = TmpArray[RightEnd];
    }
    
}

void MSort(ElementType A[], ElementType TmpArray[], int left, int right)
{
    int center;
    if(left < right){
        center = (left + right) / 2;
        MSort(A, TmpArray, left, center);
        MSort(A, TmpArray, center+1, right);
        Merge(A, TmpArray, left, center+1, right);
    }
}

void MergeSort(ElementType A[], int N)
{
    ElementType *TmpArray;
    TmpArray = (ElementType*)malloc(N * sizeof(ElementType));
    if(TmpArray != nullptr){
        MSort(A, TmpArray, 0, N-1);
        free(TmpArray);
    }
    else{
        std::cout << "NO space for tmp array" << std::endl;
    }
}

int main()
{
    int A[] = {31,41,59,26,53,58,97};
    int size = sizeof(A)/sizeof(int);
    MergeSort(A, size);
    for(int i = 0; i < size; ++i){
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

# #include <iostream>
typedef int ElementType; 

void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)
{
    int LeftEnd = Rpos -1;
    int TmpPos = Lpos;
    int NumELements = RightEnd - Lpos + 1;

    while(Lpos <= LeftEnd && Rpos <= RightEnd){
        if(A[Lpos] <= A[Rpos]){
            TmpArray[TmpPos++] = A[Lpos++];
        }
        else{
            TmpArray[TmpPos++] = A[Rpos++];
        }
    }

    while(Lpos <= LeftEnd){
        TmpArray[TmpPos++] = A[Lpos++];
    }

    while(Rpos <= RightEnd){
        TmpArray[TmpPos++] = A[Rpos++];
    }

    for (int i = 0; i < NumELements; i++, RightEnd--){
        A[RightEnd] = TmpArray[RightEnd];
    }
    
}

void MSort(ElementType A[], ElementType TmpArray[], int left, int right)
{
    int center;
    if(left < right){
        center = (left + right) / 2;
        MSort(A, TmpArray, left, center);
        MSort(A, TmpArray, center+1, right);
        Merge(A, TmpArray, left, center+1, right);
    }
}

void MergeSort(ElementType A[], int N)
{
    ElementType *TmpArray;
    TmpArray = (ElementType*)malloc(N * sizeof(ElementType));
    if(TmpArray != nullptr){
        MSort(A, TmpArray, 0, N-1);
        free(TmpArray);
    }
    else{
        std::cout << "NO space for tmp array" << std::endl;
    }
}

int main()
{
    int A[] = {31,41,59,26,53,58,97};
    int size = sizeof(A)/sizeof(int);
    MergeSort(A, size);
    for(int i = 0; i < size; ++i){
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

欢迎大家来到IT世界,在知识的湖畔探索吧!