首页 > 代码库 > 归并排序

归并排序

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是採用分治法(Divide and Conquer)的一个很典型的应用。将已有序的子序列合并,得到全然有序的序列;即先使每一个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表。称为二路归并

归并过程为:比較a[i]和a[j]的大小,若a[i]≤a[j]。则将第一个有序表中的元素a[i]拷贝到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]拷贝到r[k]中,并令j和k分别加上1,如此循环下去。直到当中一个有序表取完,然后再将还有一个有序表中剩余的元素拷贝到r中从下标k到下标t的单元。

归并排序的算法我们通经常使用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序。再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

归并操作

归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

如 设有数列{6,202,100,301。38。8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1},比較次数:3。

第二次归并后:{6,100,202,301}。{1,8,38},比較次数:4。

第三次归并后:{1,6,8,38,100,202,301},比較次数:4;

总的比較次数为:3+4+4=11,。

逆序数为14;

用途

排序

(速度仅次于高速排序。为稳定排序算法,一般用于对整体无序,可是各子项相对有序的数列,应用见2011年普及复赛第3瑞士轮的标程)

求逆序对数

详细思路是,在归并的过程中计算每一个小区间的逆序对数,进而计算出大区间的逆序对数(也能够用树状数组来求解).

技术分享

对于原始的数组2,1,3,8,5,7,6,4,10,在整个过程运行的是顺序是途中红色编号1-20。尽管我们描写叙述中说的是程序先分解,再归并,但实际过程是一边分解一边归并。前半部分分先排好序。后半部分再排好,最后整个归并为一个完整的序列,途中的merge过程它所在层的两个序列的merge过程:下图展示了每一个merge过程对作用于数组的哪部分(红色)。

技术分享

整个过程就像一个动态的树,运行顺序就是对树的先序遍历顺序。

 

C代码:

#include <stdio.h>

#include <stdlib.h>

 

void MergeArray(int a[], int temp[] , int start , int middle , int end)

{

     int i,j,s,m,e;

     i=start;

     s = start ;

     m = middle+1 ;

     e = end ;

    

     while((s <= middle)&&(m <= end))//由于包括開始和结束字符,所以用 <=

     {

         if(a[s] < a[m])

         {

              temp[i++] = a[s++] ;

         }

        

         else

         {

              temp[i++] = a[m++] ;

         }

     }

    

     while(s <= middle)

     {

         temp[i++] = a[s++] ;

     }

    

     while(m <= end)

     {

         temp[i++] = a[m++] ;

     }

    

     for(j = start ; j <= end ; j++)

     {

         a[j] = temp[j];

     }   

}

 

void MergeSort(int a[],int temp[],int start ,int end)

{

     int middle ;

     if(start < end)

     {

         middle = (start + end)/2 ;

         MergeSort(a , temp , start , middle);//通过递归层层划分,使左边有序

         MergeSort(a , temp , middle+1 , end);//右边有序

         MergeArray(a, temp , start , middle , end);//序列合并

     }

}

 

int main(int argc, char *argv[])

{

     int a[9] = {2,1,3,8,5,7,6,4,10};

     int temp[9] ;

     int i;

     MergeSort(a , temp , 0 ,8);

     for(i = 0 ; i <= 8 ; i ++)

     {

         printf("%d ",a[i]);

     }

     return 0;

}

 

归并排序