二路归并排序

in 数据结构 with 1 comment

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);
}

动图演示:

1i9Cii6gEO.gif

输出结果:

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],故相同元素的相对位置不变。这是一种稳定的排序方法。

复杂性:

较复杂

归位:

否,不是全局有序。

Responses
  1. study 一起学习 go

    Reply