联系博主


你的名字:
Email:
建议:

归并排序

编辑时间:2016-05-28      赞:7       踩:0

导言:

       本文将会介绍归并排序的原理,及其实现。通过解决POJ(北京大学的ACM在线测评平台)的第2299题来说明如何用归并排序求取数列的逆序对的个数。

正文:

       归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。---摘自百度百科


归并排序是如何进行的?
       以下为对(9,1,0,5,4)这个序列进行归并程序的过程详解。

       如图,归并排序的思想是将无序的序列拆分为两个子序列,如果子序列的元素个数大于一,则继续拆分,直至子序列中的元素个数为一。当子序列中的元素个数为一时,便开始调用合并子程序,将其合并为有序的子序列。然后,对有序的子序列再调用合并程序,与其它有序子序列合并,最后,便合并成一个有序序列了。
从上述过程可知,排序是发生在子序列的合并过程中的。所以,子序列的合并是归并排序的核心,归并排序也因此而得名。
       下面,我将以(1,9)和(0,4,5,)这两个子序列的合并为例来讲述归并排序中子序列是如何合并的。
       将(1,9)认为是左序列,(0,4,5)认为是右序列。先把左序列的最小值(1)和右序列中的最小值(0)做比较,发现(1)大于(0)。把(0)放进用于存放在临时数组中的第一位,然后把右序列的(4)拿出来,与左序列的当前值(1)相比,发现(4)大于(1)。于是,把左序列中的(1)放在临时数组的第二位,再把左序列的(9)拿出来,与右序列的当前值(4)作比较。(9)大于(4),于是,把右序列中的(4)放在临时数组中的第三位,再把右序列中的(5)拿出来与左序列中的当前值(9)作比较。(9)大于(5),把(5)放在临时数组中的第四位,然后再去从右序列取值的时候发现,右序列已经没有数值了。于是,只需把左序列中剩余的值依次放进临时数组中便可以了(因为对于每一个子序列而言,越往后,值越大)。在此例子中,左序列只剩一个(9)了,所以只需把(9)放在临时数组的第五位便可以了。这便是多个元素子序列合并的过程了,单个元素的子序列合并与上述过程一致,在这里就不再赘述了。


如何用程序来实现归并排序?
       上文讲述的都是归并排序的原理,那么具体到程序中,归并排序该如何实现?本文将以C++程序为例,通过递归来实现归并排序。

#include <iostream>
using namespace std;
/********************************************//**
 *int* mymerge(int* leftArr,int* rightArr,int leftLength,int rightLength)
 *rief 用于数组的有序合并,即合并完后是有序的数组
 *默认排序是升序(从小到大),被合并的数组都是已经排好序的
 * param leftArr:左数组,即被合并的第一个数组
 * param rightArr:右数组,被合并的第二个数组
 * param leftLength:左数组的数组长度
 * param rightLength:右数组的数组长度
 * eturn 合并好的数组地址(头指针)
 *
 ***********************************************/
int* mymerge(int* leftArr,int* rightArr,int leftLength,int rightLength){
int length=leftLength+rightLength;
//以下两个变量分别记录左序列及右序列的当前取值
int leftPos=0,rightPos=0;
//根据长度来动态申请临时数组,节省存储空间
    int* tmp=new int[length];
    bool leftEndFlag=false,rightEndFlag=false;
    for(int i=0;i<length;i++){
        if(!leftEndFlag&&!rightEndFlag){
            if(leftArr[leftPos]<=rightArr[rightPos]){
//右序列的值大于左序列,把左序列的值赋予临时数组,再取左序列的下一个值
               tmp[i]=leftArr[leftPos++];
//判断左序列是否已比较完毕
                if(leftPos>=leftLength){
                    leftEndFlag=true;
                }
            }else{
//原理同上,不过此时是左序列的值大于右序列的值
                tmp[i]=rightArr[rightPos++];
                if(rightPos>=rightLength){
                    rightEndFlag=true;
                }
            }
        }else if(leftEndFlag){
//左序列已经没有数值可以比较了,此时只需把右序列中剩余的值复制到临时数组中便可以了
            tmp[i]=rightArr[rightPos++];
        }else if(rightEndFlag){
//右序列的值已比较完毕,此时只需把左序列中剩余的值复制到临时数组中便可以了           
  tmp[i]=leftArr[leftPos++];
        }
    }
    return tmp;
}

/********************************************//**
 *int* MergeSort(int* arr,int start,int length)
 * rief 用归并排序对目标数组进行排序,返回排序后的新数组
 * param arr:目标数组
 * param start:从目标数组中下标为start的数开始排序
 * param length:要排序的个数
 * eturn 排序后的新数组
 *
 ***********************************************/
int* MergeSort(int* arr,int start,int length){
    int *leftTmp,*rightTmp,*tmp,*oneTmp=new int[1];
    int middle=(int)(length/2)+start;
    int a[1],b[1];
if(length>=3){
//把当前序列分为左序列与右序列后,在进行归并排序
        leftTmp=MergeSort(arr,start,middle-start);
        rightTmp=MergeSort(arr,middle,start+length-middle);
}else if(2==length){
//当前序列只剩两个元素,直接合并便可以了
        a[0]=arr[start];
        b[0]=arr[start+1];
        return mymerge(a,b,1,1);
}else{
//当前序列只有一个元素,不需合并直接返回当前值就可以了
        oneTmp[0]=arr[start];
        return oneTmp;
    }
tmp=mymerge(leftTmp,rightTmp,middle-start,start+length-middle);
//释放临时数组的内存
    delete leftTmp;
delete rightTmp;
//返回排好序的数组
    return tmp;
}
int main(){
    int a[]={9,1,0,5,4,3};
    int *b=MergeSort(a,0,6);
    for(int i=0;i<6;i++){
        cout<<b[i]<<endl;
    }
    return 0;
}

       上述程序中的注释已经对程序做了很详细的讲解,我就不再叙述了。然而,虽然程序实现了归并排序,也易于理解。但是,频繁地分配和释放内存会极大地影响程序的效率。在讲解如何用归并排序求取序列的逆序对个数时,我会顺便讲解如何对上诉程序进行优化,然而,接下来我先要讲述如何求取归并排序的时间复杂度O(n)。


如何求取归并排序的时间复杂度?
       归并排序的时间复杂度为O(n)=n log⁡n  。那这个结果是如何得出来的?
       在这里,我将采用分析算法逻辑的方法来求取归并排序的时间复杂度。当然,你也可以利用一些数学方法来求取归并排序的时间复杂度。在这里,我向大家推荐一篇利用数学中的「归纳假设法」来求解归并排序时间复杂度的文章。文章写得既简单易懂又不缺严谨,只需一点数学知识便可看懂,极力推荐大家去看一看。传送门在此→http://www.codelast.com/原创-如何用「归纳假设法」求归并排序的时间复/
       回归正题,从上面的例子和程序,我们不难发现。归并排序每次会把当前的序列一分为二,若当前序列无法再分时,便调用合并程序,对子序列进行合并排序然后返回,然后再对返回的已排好序的两个子序列进行合并排序。这样的话你可以手动模拟出一颗二叉树来。于是,便有:O(n) =每一层的总计算量×总的层数,每一层的计算量即合并程序的子程序的计算量,总的层数即递归的次数。
       先求合并程序的时间复杂度,假设n=i+j,对i个和j个数进行合并,合并子程序会进行n次循环,每次循环会得出一个较小数,然后将其赋给临时数组。于是,合并程序的时间复杂度变为O(n)=i+j=n。
       再求递归的层数,假设递归的层数为x,对n个数进行归并排序。由于会对n个数不停地进行二分,直至当前序列只有一个元素,则可以得出2^(x-1)。对于最坏情况,n=2^x,即x=log2n

       至此,可得O(n)= n log2⁡n。在描述算法复杂度的时候,对数的底数无关紧要,通常省略它,因此,归并排序的时间复杂度一般记为: O(n)=nlogn。


如何用归并排序求解序列中的逆序对个数?
       在此,我将通过POJ的第2299题,来说明如何用归并排序求解序列中的逆序对个数。
       题目大意为:给出长度为n的无序序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列,限时7000毫秒(即7000毫秒内必须给出结果)。初看题目觉得可以用冒泡解决,然而,题目要求,n < 500000,并且序列中的值的取值范围是:0 ≤ x ≤ 999,999,999。这样一来,即使有7000毫秒,冒泡也会歇菜。
       如果相邻的两个元素满足前一个大于后一个,则肯定要交换一次,因为最终位置是小的在前,大的在后。因此本题其实就是求原序列(数组)中的逆序对的数目。
       两个数(a, b)的排列,若满足a > b,则称之为一个逆序对。
       求逆序对可以用归并排序,因为在两个子序列的合并过程中左序列的值会与右序列的值进行比较,此时便可算出每一次合并中的逆序对数。把一次合并的逆序对的个数加起来,便可得到整个序列的逆序对个数。
       下面是我解题的程序,其中使用的内存为 8544K,耗时 3313MS。
#include <iostream>
#define NMAX 500010
using namespace std;
//题目的结果会超过long的取值范围,所以要用long long类型存储
long long cnt=0;
void mymerge(long long* newArr,long long *arr,long left,long middle,long right){
    long leftPos=left,rightPos=middle;
    bool leftEndFlag=false,rightEndFlag=false;
    if(1==(right-left)){
        newArr[left]=arr[left];
        return;
    }
    for(long i=left;i<right;i++){
        if(!leftEndFlag&&!rightEndFlag){
            if(arr[leftPos]<=arr[rightPos]){
                newArr[i]=arr[leftPos++];
                if(leftPos>=middle){
                    leftEndFlag=true;
                }
            }else{
                newArr[i]=arr[rightPos++];
//要加上leftPos右边的值的个数,因为leftPos右边的值都比leftPos的值大。所以,leftPos右边的值也都会比当前的rightPos的值大,而一旦当前rightPos的值赋值给临时数组后,这些情况就会被忽略。所以,如果计数器的值只是加一,那么计数器的值就会偏小                
                cnt=cnt+(middle-leftPos);
                if(rightPos>=right){
                    rightEndFlag=true;
                }
            }
        }else if(leftEndFlag){
            newArr[i]=arr[rightPos++];

        }else if(rightEndFlag){
            newArr[i]=arr[leftPos++];
        }
    }

//必须把临时数组的值赋给原数组,不然递归返回后进行合并的两个子序列是没进行排序的子序列。
    for(int i=left;i<right;i++){
        arr[i]=newArr[i];
    }
}
void  MergeSort(long long* sortArr,long long* arr,long start,long length){
    long middle=(long)(length/2)+start;
    if(length>=3){
        MergeSort(sortArr,arr,start,middle-start);
        MergeSort(sortArr,arr,middle,start+length-middle);
    }else if(2==length){
        return mymerge(sortArr,arr,start,start+1,start+2);
    }else{
        return mymerge(sortArr,arr,start,middle,start+1);
    }
    mymerge(sortArr,arr,start,middle,start+length);
    return;
}
int main(){
// 必须用long long类型存储数值,不然,通不过测试
    long long a[NMAX]={0},sorta[NMAX]={0};
    long i=0,n=0;
    cin>>n;
    while(0!=n){
        cnt=0;
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        MergeSort(sorta,a,0,n);
        cout<<cnt<<endl;
        cin>>n;
    }
    return 0;
}

       在主程序中我开了一个与存放运算序列相同大小的临时数组,目的是将其充当合并过程中的临时数组。这样虽然浪费了大量空间,却避免了动态内存的分配,大大提高了程序的效率。当然,要3000多毫秒才能通过测试,显然还有很大的优化空间,大家可以尝试去继续优化这个程序,这里我就不叙述了。
       值得注意的是,输出的结果会超出long类型,必须要使用long long类型来存储输出结果,序列中的值也会超出long的存储范围,所以也要用long long类型存储。要使用long long类型的变量,那便要使用测试平台的g++编译编译器,而不是测试平台的c++编译器,不然同样无法通过测试。由于超出本文论述范围,这里就不赘述原因了。如果在做题过程中有什么疑问,可以去评论区找找原因,里面有很多大神的评论,相信能给大家帮助。
       至此,归并排序的内容便讲述完毕了。如果发现本文的论述有错误,可以联系我,我会尽量去核实的。感谢大家的支持。


POJ第2299题的链接:
http://poj.org/problem?id=2299

转载请注明:
    本文转载自:www.kantblog.com/blog/Algorithm/prearti/1

Kant©2016 All rights reserved 粤ICP备16014517号