二路归并排序(merge sort)
标签: 数据结构
学习人数: 29.9k

前言

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

 

算法思想

该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

动态效果示意图:

排序(7):归并排序

分而治之:

1、分阶段

排序(7):归并排序

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为logn。

2、治阶段
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

排序(7):归并排序

排序(7):归并排序

 

代码实现

#include <stdio.h>
#define MAX 1000001

int a[MAX], b[MAX];
//将两段有序的区间合并为一段,复杂度为线性
void Merge(int a[], int low, int mid, int high) {
    int i = low, j=mid+1, k = low;
    while(i!=mid+1 && j!=high+1) {
        if(a[i] >= a[j])
            b[k++] = a[j++];
        else
            b[k++] = a[i++];
    }
    while(i != mid+1)
        b[k++] = a[i++];
    while(j != high+1)
        b[k++] = a[j++];
    for(i=low; i<=high; i++)
        a[i] = b[i];
}
//归并排序
void MergeSort(int a[], int low, int high) {
    int mid;
    if(low < high) {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);//前面部分
        MergeSort(a, mid+1, high);//后面的部分
        Merge(a, low, mid, high);//合并
    }
}
int main() {
    int i, n;
    scanf("%d",&n);
    for(i=0; i<n; i++) scanf("%d",&a[i]);
    MergeSort(a, 0, n-1);
    for(i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

 

算法分析

1、归并排序算法的性能

排序(7):归并排序

其...

登录查看完整内容


课后作业

课后习题

 

【2012年真题】设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和 200 个数据元素,各 表中元素按升序排列。要求通过 5 次两两合并,将 6 个表最终合并成 1 个升序表,并在最坏情况下比较 的总次数达到最小。请问答下列问题。 
1)给出完整的合并过程,并求出最坏情况下比较的总次数。 
2)根据你的合并过程,描述 N(N≥2)个不等长升序表的合并策略,并说明理由。 

参考答案:
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中Merge()函数;对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 
1)对于长度分别为 m,n 的两个有序表的合并,最坏情况下是一直比较到两个表尾元素,比较次数为 m+n-1 次。故,最坏情况的比较次数依赖于表长,为了缩短总的比较次数,根据哈夫曼树(最佳归并树)思想的启发,可采用如图所示的合并顺序。 

根据上图中的哈夫曼树,6 个序列的合并过程为: 
第 1 次合并:表 A 与表 B 合并,生成含有 45 个元素的表 AB; 
第 2 次合并:表 AB 与表 C 合并,生成含有 85 个元素的表 ABC; 
第 3 次合并:表 D 与表 E 合并,生成含有 110 个元素的表 DE; 
第 4 次合并:表 ABC 与表 DE 合并,生成含有 195 个元素的表 ABCDE; 
第 5 次合并:表 ABCDE 与表 F 合并,生成含有 395 个元素的最终表。 
由上述分析可知,最坏情况下的比较次数为:第 1 次合并,最多比较次数=10+35-1=44;第 2 次合并,最多比较次数=45+40-1=84;第 3 次合并,最多比较次数=50+60-1=109;第 4 次合并,最多比较次数=85+110-1=194;第 5 次合并,最多比较次数=195+200-1=394。 
故,比较的总次数最多为:44+84+109+194+394=825 
2)各表的合并策略是:在对多个有序表进行两两合并时,若表长不同,则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想,依次选择最短的两个表进行合并,可以获得最坏情况下最佳的合并效率。 


登录后开始许愿

暂无评论,来抢沙发