Merge Sort

Merge Sort

五月 29, 2021

（2路）归并排序（倒置的二叉树：两两合并排序后再合并）

  1. 二路归并思路：n个记录看作n个序列，两两归并后得到$\lfloor n/2 \rfloor$个长度为2或1的有序子序列，再次循环归并直到得到一条长度为n的序列

  2. ==递归==思路进行归并排序（先拆分，后归并）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void MSort(int SR[] , int TR1[] , int s , int t)
    {
        int m;
        int TR2[MAXSIZE+1];
        if(s==t)
        {
            TR1[s]=SR[s];
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    /*
    子区间SR[i...m](下标用k存放)、子区间SR[m+1...n]（下标用j存放） ===> TR[i....n]
    */
    void Merge(int SR[] , int TR)
    {
        int j,k,i;
        /*****从小到大归并入TR*****/
        for(j=m+1,k=i ; i<=m && j<=n ; k++)
        {
            if(SR[i] < SR[j])
            {
                TR[k] = SR[i++];	//左SR间元素并入
            }
            else
            {
                TR[k] = SR[j++];	//右SR元素并入
            }
        }
        /******左右子序列进行元素判断******/
        if(i<=m)
        {
            for(l=0 ; l<=m-i ; l++)
            {
                TR[k+l] = SR[i+l]；
            }
        }
        if(j<=n)
        {
            for(l=0 ; l<=n-j ; l++)
            {
                TR[k+l] = SR[j+l];
            }
        }
    }

  3. ==迭代==思路进行归并排序

    1. 相邻元素归并：判断序列为奇偶，奇序列需要对最后一个单元素进行处理
    2. 数组复用：S数组当成T数组，T数组当成S数组
    3. 合并元素数从k = 1成倍增加（log2n）【1、1x2、2x2、4x2…】
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void MergeSort2(SqList *L)
    {
        int *TR=(int*)malloc(L->length * sizeof(int));	//存放归并结果，动态生成归并数据空间
        int k=1;
        while(k<L->length)
        {
            MergePass(L->r , TR , k , L->length);	
            k=2*k;
            MergePass(TR , L->r , k , L->length);
            k=2*k;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    void MergePass(int SR[] , int TR[] , int s , int n)
    {
        int i=1;
        int j;
        /****调用两两归并(采用相邻两个元素归并的方式)****/
        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);
        }
        */
        /******奇数序列，对最后一个元素进行处理*******/
        if(i > n)
        {
            for(j = i ; j <= n ; j++)
            {
                TR[j] = SR[j];
            }
        }
    }
  1. 1. （2路）归并排序（倒置的二叉树：两两合并排序后再合并）