归并排序代码实现

Dear 丶 2022-08-09 18:37 136阅读 0赞

一、递归代码实现

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    using namespace std;
    
    #define  MAXSIZE  10
    
    /* 将有序的SR[i..m]和SR[m+1...n],归并为有序的TR[i..n] */
    void Merge(int SR[], int TR[], int i, int m, int n);
    
    /* 归并排序 */
    void MSort(int SR[], int TR1[], int  s, int t);
    
    
    /* 归并排序,递归实现 */
    void MSort(int SR[], int TR1[], int  s, int t)
    {
        int m = 0;
        int TR2[MAXSIZE+1] = {0};
    
        if (s == t)
        {
            TR1[s] = SR[s];
        }
        else
        {
            m = (s+t)/2;
            MSort(SR,TR2,s,m);
            MSort(SR,TR2,m+1,t);
    
            Merge(TR2,TR1,s,m,t);
        }
    
    }
    
    /* 将有序的SR[i..m]和SR[m+1...n],归并为有序的TR[i..n] */
    void Merge(int SR[], int TR[], int i, int m, int n)
    {
        int j = 0, k = 0, l = 0;
    
        /* 将SR中记录从小到大归并入TR */
        for(j = m+1,k = i; i <= m && j <= n; k++)
        {
            if (SR[i] < SR[j])
            {
                TR[k] = SR[i++];
            }
            else
            {
                TR[k] = SR[j++];
            }
        }
    
        /* 将剩余的SR[i..m]复制到TR */
        if (i <= m)
        {
            for(l = 0; l <= m-i; l++)
            {
                TR[k+l] = SR[i+l];
            }
        }
    
        /* 将剩余的SR[j..n]复制到TR */
        if (j <= n)
        {
            for(l = 0; l <= n-j; l++)
            {
                TR[k+l] = SR[j+l];
            }
        }
    }
    
    
    int main(void)
    {
        int i = 0;
        int a[10] = {0,23,56,3,1,100,24,67,77,102};
    
        /* 归并排序 */
        MSort(a,a,1,9);
    
        for(i = 1; i < 10; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

二、非递归代码实现

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    using namespace std;
    
    #define  MAXSIZE  10
    
    /* 将有序的SR[i..m]和SR[m+1...n],归并为有序的TR[i..n] */
    void Merge(int SR[], int TR[], int i, int m, int n);
    
    /* 将SR中相邻长度为s的子序列两两归并到TR[] */
    void mergePass(int SR[], int TR[], int s, int n);
    
    /* 归并排序，非递归代码实现 */
    void MSort(int a[], int length);
    
    
    /* 归并排序，非递归代码实现 */
    void MSort(int a[], int length)
    {
        int *TR = new int[length];
        int k = 1;
    
        while(k < length)
        {
            mergePass(a,TR,k,length);
            k = 2*k;
            mergePass(TR,a,k,length);
            k = 2*k;
        }
    
        delete []TR;
    }
    
    /* 将SR中相邻长度为s的子序列两两归并到TR[] */
    void mergePass(int SR[], int TR[], int s, int n)
    {
        int i = 1;
        int j = 0;
    
        while(i <= n-2*s+1)
        {
            Merge(SR,TR,i,i+s-1,i+2*s-1);
            i = i + 2*s;
        }
    
        /* 归并最后两个序列 */
        if (i < n-s+1)
        {
            Merge(SR,TR,i,i+s-1,n);
        }
        /* 若最后剩下单个子序列 */
        else
        {
            for(j = i; j <= n; j++)
            {
                TR[j] = SR[j];
            }
        }
    }
    
    
    
    /* 将有序的SR[i..m]和SR[m+1...n],归并为有序的TR[i..n] */
    void Merge(int SR[], int TR[], int i, int m, int n)
    {
        int j = 0, k = 0, l = 0;
    
        /* 将SR中记录从小到大归并入TR */
        for(j = m+1,k = i; i <= m && j <= n; k++)
        {
            if (SR[i] < SR[j])
            {
                TR[k] = SR[i++];
            }
            else
            {
                TR[k] = SR[j++];
            }
        }
    
        /* 将剩余的SR[i..m]复制到TR */
        if (i <= m)
        {
            for(l = 0; l <= m-i; l++)
            {
                TR[k+l] = SR[i+l];
            }
        }
    
        /* 将剩余的SR[j..n]复制到TR */
        if (j <= n)
        {
            for(l = 0; l <= n-j; l++)
            {
                TR[k+l] = SR[j+l];
            }
        }
    }
    
    
    int main(void)
    {
        int i = 0;
        int a[10] = {0,23,56,3,1,100,24,67,77,102};
    
        /* 归并排序 */
        MSort(a,9);
    
        for(i = 1; i < 10; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    
        return 0;
    }