并归排序法

归并就是将多个已排序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge)。归并排序就是利用归并技术来进行排序，两两归并最后变为有序的序列。

并归排序法详细介绍

归并就是将多个已排序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge)。归并排序就是利用归并技术来进行排序，两两归并最后变为有序的序列。

并归排序法基本思路

1、算法基本思路

设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A，A，将它们归并为一个有序数列，并存储在A。

为了减少数据移动次数，不妨采用一个临时工作数组C，将中间排序结果暂时保存在C数组中，等归并结束后，再将C数组值复制给A。

归并过程中，设置p1，p2和p3三个指针，其初值分别指向三个有序区的起始位置。归并时依次比较A和A的关键字，取关键字较小的记录复制到C中，然后将被复制记录的指针p1或p2加1，以及指向复制位置的指针p3加1。

重复这一过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制到C中即可。

2）

（1）自底向上的基本思想

自底向上的基本思想是：第1趟归并排序时，将数列A看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第1趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。

上述的每次归并操作，均是将两个有序序列合并成一个有序序列，故称其为“二路归并排序”。

思路

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

并归排序法参考代码

void mergSort(int* a,int low,int mid,int high)

{

int * p=new int;

int i=low;

int j=low;

int h=mid+1;

while(h<=high&&j<=mid)

{

if(a<=a)

{

p=a;

j++;

i++;

}

else

{

p=a;

h++;

i++;

}

}

for(;j<=mid;j++,i++)

{

p=a;

}

for(;h<=high;h++,i++)

{

p=a;

}

for(i=low;i<=high;i++)

{

a=p;

}

delete p;

}

void merg(int* a,int low,int high)

{

if(low<high)

{

int mid=(low+high)/2;

merg(a,low,mid);

merg(a,mid+1,high);

mergSort(a,low,mid,high);

}

}