计算机程序设计艺术-----归并排序

合并排序：把两个或多个有序序列合并为一个有序的序列。

例子：

合并503,703,765和087,512,677，得到087,503,512,677,703,765。每次比较两个序列最小的数，输出最小的，不断重复这个过程。

如:

 <!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter" /> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0" /> <v:f eqn="sum @0 1 0" /> <v:f eqn="sum 0 0 @1" /> <v:f eqn="prod @2 1 2" /> <v:f eqn="prod @3 21600 pixelWidth" /> <v:f eqn="prod @3 21600 pixelHeight" /> <v:f eqn="sum @0 0 1" /> <v:f eqn="prod @6 1 2" /> <v:f eqn="prod @7 21600 pixelWidth" /> <v:f eqn="sum @8 21600 0" /> <v:f eqn="prod @7 21600 pixelHeight" /> <v:f eqn="sum @10 21600 0" /> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" /> <o:lock v:ext="edit" aspectratio="t" /> </v:shapetype><v:shape id="图片_x0020_4" o:spid="_x0000_i1029" type="#_x0000_t75" style='width:106.5pt;height:36.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image001.png" o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

得到：

<!--[if gte vml 1]><v:shape id="图片_x0020_7" o:spid="_x0000_i1028" type="#_x0000_t75" style='width:130.5pt; height:45pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image003.png" o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

然后：

<!--[if gte vml 1]><v:shape id="图片_x0020_10" o:spid="_x0000_i1027" type="#_x0000_t75" style='width:141.75pt; height:30pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image005.png" o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

接着：

<!--[if gte vml 1]><v:shape id="图片_x0020_13" o:spid="_x0000_i1026" type="#_x0000_t75" style='width:162.75pt; height:29.25pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image007.png" o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

直到一个序列被取尽。

流程图，如下：

<!--[if gte vml 1]><v:shape id="图片_x0020_1" o:spid="_x0000_i1025" type="#_x0000_t75" style='width:272.25pt; height:159.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01\clip_image009.png" o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

代码如下：

     private void Merge(int seq1[],int start1,int end1,int[]seq2,int start2,int end2 ){

     int [] mergeSeq=new int [end1+end2-start1-start2];

     int i=0;

     while(start1<=end1||start2<=end1){

         if(start1>end1||seq1[start1]>seq2[start2]){

             mergeSeq[i]=seq2[start2];

             start2++;

             i++;

         }

         else if(start2>end2 ||seq1[start1]<=seq2[start2]){

             mergeSeq[i]=seq1[start1];

             mergeSeq[i]=seq1[start1];

             start1++;

             i++;

         }

     }

     }

归并排序：采用分治法（Divide and Conquer）和合并排序的一种排序算法；

基本思想：把序列R[start…end]划分为R[start…middle]和R[middle…end],对R[start…middle]和R[middle…end]分别用合并排序，直到被划分的序列为只包含一个元素为止。再对R[start…middle]和R[middle…end]进行合并排序。

实例：

数组A有7个数据，分别是： 49   38   65  97   76   13   27，那么采用归并排序算法的操作过程如图7所示：

　　初始值                 [49]   [38]   [65]   [97]   [76]   [13]   [27]

　　看成由长度为1的7个子序列组成

　　第一次合并之后         [38     49]    [65    97]   [13     76]   [27]

看成由长度为1或2的4个子序列组成

　　第二次合并之后         [38     49      65    97]   [13     27     76]

看成由长度为4或3的2个子序列组成

第三次合并之后         [13     27      38    49     65      76    97]

 

 

代码实现：

void Merge(SeqList R，int low，int m，int high)
    {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的
     //子文件R[low..high]
     int i=low，j=m+1，p=0； //置初始值
     RecType *R1； //R1是局部向量，若p定义为此类型指针速度更快
     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；
     if(! R1) //申请空间失败
       Error("Insufficient memory available!")；
     while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
       R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；
     while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中
       R1[p++]=R[i++]；
     while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中
       R1[p++]=R[j++]；
     for(p=0，i=low；i<=high；p++，i++)
       R[i]=R1[p]；//归并完成后将结果复制回R[low..high]
    } //Merge