大话数据结构-9.8 归并排序 - 高飞网

9.8 归并排序

2017-02-06 10:37:53.0

9.8.1 归并排序算法

    归并排序(Merging Sort)是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2](不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直到得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序。


归并排序的代码:

#include "sort.h"
/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/
void Merge(int SR[],int TR[],int i,int m,int n)
{
        int j,k,l;
        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++];
                }
        }       
        if(i<=m)
        {
                for(l=0;l<=m-i;l++)
                {
                        TR[k+l]=SR[i+l];/*将剩余的SR[i..m]复制到TR中*/
                }
        }
        if(j<=n)
        {
                for(l=0;l<=n-j;l++)
                {
                        TR[k+l]=SR[j+l];/*将剩余的SR[j..n]复制到TR中*/
                }
        }
}
/*将SR[s..t]归并排序为TR1[s..t]*/
void MSort(int SR[],int TR1[],int s,int t)
{
        int m;
        int TR2[MAXSIZE+1];
        if(s==t)
        {
                TR1[s]=SR[s];
        }
        else
        {
                m=(s+t)/2;/*将SR[s..t]平分为SR[s..m]和SR[m+1...t*/
                MSort(SR,TR2,s,m);/*递归将SR[s..m]归并为有序的TR2[s..m]*/
                MSort(SR,TR2,m+1,t);/*递归将SR[m+1..t]归并为有序的TR2[m+1..t]*/
                Merge(TR2,TR1,s,m,t);/*将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]*/
        }
}
void MergeSort(SqList* L)
{
        MSort(L->r,L->r,1,L->length);
}


    例如将数组{50,10,90,30,70,40,80,60,20}进行排序,L->length=9。归并排序的实现步骤如下:

1传入数组,SR与TR1都是{50,10,90,30,70,40,80,60,20},此时s=1,t=9,s!=t,m=(1+9)/2=5
2

将数组分成两部分分别排序,即MSort(SR,TR2,1,5)和MSort(SR,TR2,6,9)


3将上面分开的两个子序列,分别进行排序(假设已有序)


4继续递归



5总步骤概览


再来看看核心的Merge是如何排序的:

1执行for循环,对分开的两个子序列分别从头比较,并依次放入到TR中


2对于比较剩下的部分数组,直接拷贝到新数组当中


9.8.2 归并排序复杂度分析

    时间复杂度:O(nlogn)。

    空间复杂度:O(n+logn)。

    由于Merge函数中有if(SR[i]<SR[j])的语句,因此说明是两两比较,不存在跳跃,因此归并排序是稳定的排序算法。

    归并排序是一种比较占用内存,但却效率高且稳定的算法。


9.8.3 非递归实现归并排序

    非递归实现归并排序代码:

#include "sort.h"
#include<stdlib.h>
/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/
void Merge(int SR[],int TR[],int i,int m,int n)
{
        int j,k,l;
        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++];
                }
        }       
        if(i<=m)
        {
                for(l=0;l<=m-i;l++)
                {
                        TR[k+l]=SR[i+l];/*将剩余的SR[i..m]复制到TR中*/
                }
        }
        if(j<=n)
        {
                for(l=0;l<=n-j;l++)
                {
                        TR[k+l]=SR[j+l];/*将剩余的SR[j..n]复制到TR中*/
                }
        }
}
/*将SR[]中相邻长度为s的子序列两两归并到TR[]*/
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);
        }
        else
        {/*若最后只剩下单个子序列*/
                for(j=i;j<=n;j++)
                {
                        TR[j]=SR[j];
                }
        }
}
void MergeSort(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传入数组为{50,10,90,30,70,40,80,60,20},此时s=1,t=9,开辟新的内存存放归并结果
2while循环,k为子序列的长度,它的变化为1→2→4→8→16

3当k=1时,MergePass函数将原来的无序数组两两归并入TR


4当k=2时,MergePass函数将TR中两两有序的序列再次归并回数组L.r中


5当k=4时,因为k<9,继续循环,最后


    非递归的迭代方法,避免了递归时深度为log2n的栈空间,空间只是用到申请归并临时用的TR数组,因此空间复杂度为O(n),并且避免递归也在时间性能上有一定的提升。因此,使用归并排序时,尽量考虑用非递归方法。

上一篇:9.7 堆排序 396
下一篇:9.9 快速排序 417