首页 > 代码库 > 归并排序
归并排序
归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是採用分治法(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;
}
归并排序