二路归并排序

1.排序思路

自上而下考虑：
将R[0..n-1]分成两个子区间a1，a2。
继续分a1，a2，直至子区间长度为1
依次归并各个子区间，最后得到长度为n的有序序列。

自下而上考虑：
将R[0..n-1]看成是n个长度为1的有序序列，
将k个长度为m的有序序列进行两两归并，得到（k/2向上取整）个长度为2m的有序序列（最后一个有序序列长度可能小于2m）
重复上述过程，直至k=1，m>=n。得到一个长度为n的有序序列。

2.排序算法

以c为例,从小到大排序：

自上而下考虑：

#include<stdio.h>

void merge(int R[],int low,int mid,int high){
    int i=low,j=mid+1,k=0;
    int tmp[high-low+1];//临时变量，存储归并后数据
    while(i<=mid&&j<=high){
        if(R[i]<=R[j]){
            tmp[k++]=R[i++];
        }else{
            tmp[k++]=R[j++];
        }     
    }
    //两个区间不一样长时，需要将较长的那个区间剩余的部分拷贝到tmp里
    while(i<=mid){
        tmp[k++]=R[i++];
    }
    while(j<=high){
        tmp[k++]=R[j++];
    }
    for(k=0,i=low;i<=high;){
        printf("%d ", tmp[k]);//打印一次归并后的结果
        R[i++]=tmp[k++];
    }
    printf("\n");
}

void merge_sort(int R[],int low,int high){
    int mid;
    if(low<high){
        mid=(low+high)/2;
        merge_sort(R,low,mid);
        merge_sort(R,mid+1,high);
        merge(R,low,mid,high);
    }
}
int main(void){
    int a[] = {9,8,7,6,5,4,3,2,1,0};
    merge_sort(a,0,9);
}

动图演示：

输出结果：

8 9
7 8 9
5 6
5 6 7 8 9
3 4
2 3 4
0 1
0 1 2 3 4
0 1 2 3 4 5 6 7 8 9

自下而上考虑：

#include<stdio.h>
//merge归并代码同上
void merge(int R[],int low,int mid,int high){
    int i=low,j=mid+1,k=0;
    int tmp[high-low+1];//临时变量，存储归并后数据
    while(i<=mid&&j<=high){
        if(R[i]<=R[j]){
            tmp[k++]=R[i++];
        }else{
            tmp[k++]=R[j++];
        }     
    }
    //两个区间不一样长时，需要将较长的那个区间剩余的部分拷贝到tmp里
    while(i<=mid){
        tmp[k++]=R[i++];
    }
    while(j<=high){
        tmp[k++]=R[j++];
    }
    for(k=0,i=low;i<=high;){
        printf("%d ", tmp[k]);//打印一次归并后的结果
        R[i++]=tmp[k++];
    }
    printf("\n");
}
void mergepass(int R[],int length,int n){
    int i;
    for(i=0;i+2*length-1<n;i+=2*length){//归并两个长为length的相邻子表
        merge(R,i,i+length-1,i+2*length-1);
    }
    if(i+length-1<n-1)//如果余下的两个子表，后者长度小于length，归并它们
        merge(R,i,i+length-1,n-1);
}

void merge_sort1(int R[],int n){
    int length;
    for(length=1;length<n;length*=2){//进行log2n趟排序
        mergepass(R,length,n);
    }
}
int main(void){
    int a[] = {9,8,7,6,5,4,3,2,1,0};
    merge_sort1(a,10);
}

输出结果：

8 9
6 7
4 5
2 3
0 1
6 7 8 9
2 3 4 5
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

3.算法分析

时间复杂度：

二路归并需要进行ceil(log~2~n)趟，每趟时间为O(n)，故其时间复杂度为O(nlog~2~n)

空间复杂度：

int tmp[high-low+1]，最后一次归并需要所有元素参与，所以空间复杂度为O(n)

稳定性：

插入时判断条件为R[i]<=R[j]，故相同元素的相对位置不变。这是一种稳定的排序方法。

复杂性：

较复杂

归位：

否，不是全局有序。

本文由 ukuq 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 30, 2019 at 09:39 pm