归并排序

作者: veaxen 分类: 数据结构与算法 发布时间: 2017-03-25 05:17

本文是转载自http://blog.csdn.net/ivan_zgj/article/details/51446520
只是做了一些描述上的修改。

归并排序是分治思想的一种应用,把复杂大型的问题切分成若干个小问题,在进行一一解决然后进行合并,最后把复杂的问题解决。
先看一个简单的排序程序,这个程序是对两个有序数组进行合并,合并后的数组依然是有序的数组:

int *merge(const int *arry1,const int *arry2,const int len1,const int len2){
    int *result = (int*)malloc(sizeof(int)*(len1+len2));
    int *ptr = result;
    int i,j;
    i = 0;
    j = 0;
    while(i<len1&&j<len2){
        if(*a1<*a2){
            *ptr++ = *arry1++;
            i++;
        }
        else{
            *ptr++ = *arry2++;
            j++;
        }
    }
    while(i<len1){
        *ptr++ = *arry1++;
        i++;
    }
    while(j<len2){
        *ptr++ = *arry2++;
        j++;
    }
    return result;
}

这里合并的方法非常简单,就是对两个数组进行遍历,将较小的元素插入新数组当中,因为a1,a2数组原本就是有序的所以这样合并得到的结果依然是有序的,上述代码是按照从小到大的顺序。
假设两个数组分别是{0,1,2,3},{1,3,4,5},那么上述合并过程可以描述如下:

result = {0}, i=1 , j=0
result = {0,1}, i=1 , j=1
result = {0,1,1}, i= 2 , j=1
result = {0,1,1,2},i=3 , j=1
result = {0,1,1,2,3},i=4 , j=1

此时跳出第一个while循环,然后有j < n2,进入while(j < n2)循环

result = {0,1,1,2,3,3},i=4 , j=2
result = {0,1,1,2,3,3,4},i=4 , j=3
result = {0,1,1,2,3,3,4,5},i=4 , j=4

程序结束,得到一个新的数组 {0,1,1,2,3,3,4,5}。
归并排序就是基于上述算法,利用分治的思想实现的。假设要对8个元素进行归并排序,其归并过程如其归并树所示:
这里写图片描述
其实归并排序是一个自底向上的过程,例如上图中的8元素数组,其先将数组划分成单元素,然后相邻两个元素进行合并,得到4个新的有序数组,然后继续相邻两个数组进行合并,得到两个新的有序数组,最后再合并得到数组排序后的结果。上图的归并树的每一层的合并过程,不管是多少组数组进行两两合并,其过程也只是遍历一次原数组的全部元素而已,故其时间复杂度为O(n),而树的高度为lg(n),所以归并排序的时间复杂度为O(nlg(n))。

void merge_sort(int *arry,const int len){
    int *result,i;
    if(len<=1){
        return;
    }
    merge_sort(arry,len/2);
    merge_sort(arry+len/2,len-len/2);
    result = merge(arry,arry+len/2,len/2,len-len/2);
    for(i=0;i<len;i++){
        *arry++ = *(result+i);
    }
    free(result);
}

由于归并排序是一种变址排序,所以上述代码在归并完成后需要对原数组重新赋值。其实如果没有必要,也可以不这样做,直接返回排序后的数组即可。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据