归并算法

归并排序法 ：

百科链接

说明：
归并排序比较占用内存，但却是一种效率高而且稳定的算法。

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（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；
描述：
归并操作的工作原理如下：

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针超出序列尾
  将另一序列剩下的所有元素直接复制到合并序列尾
  Java语言

package　algorithm;
public　class　MergeSort　{
    //　private　static　long　sum　=　0;
    /**
    　*　<pre>
    　*　二路归并
    　*　原理：将两个有序表合并和一个有序表
    　*　</pre>
    　*　
    　*　@param　a
    　*　@param　s
    　*　第一个有序表的起始下标
    　*　@param　m
    　*　第二个有序表的起始下标
    　*　@param　t
    　*　第二个有序表的结束小标
    　*　
    　*/
    private　static　void　merge(int[]　a,　int　s,　int　m,　int　t)　{
        int[]　tmp　=　new　int[t　-　s　+　1];
        int　i　=　s,　j　=　m,　k　=　0;
        while　(i　<　m　&&　j　<=　t)　{
            if　(a[i]　<=　a[j])　{
                tmp[k]　=　a[i];
                k++;
                i++;
            }　else　{
                tmp[k]　=　a[j];
                j++;
                k++;
            }
        }
        while　(i　<　m)　{
            tmp[k]　=　a[i];
            i++;
            k++;
        }
        while　(j　<=　t)　{
            tmp[k]　=　a[j];
            j++;
            k++;
        }
        System.arraycopy(tmp,　0,　a,　s,　tmp.length);
    }
    /**
    　*　
    　*　@param　a
    　*　@param　s
    　*　@param　len
    　*　每次归并的有序集合的长度
    　*/
    public　static　void　mergeSort(int[]　a,　int　s,　int　len)　{
        int　size　=　a.length;
        int　mid　=　size　/　(len　<<　1);
        int　c　=　size　&　((len　<<　1)　-　1);
        //　-------归并到只剩一个有序集合的时候结束算法-------//
        if　(mid　==　0)
            return;
        //　------进行一趟归并排序-------//
        for　(int　i　=　0;　i　<　mid;　++i)　{
            s　=　i　*　2　*　len;
            merge(a,　s,　s　+　len,　(len　<<　1)　+　s　-　1);
        }
        //　-------将剩下的数和倒数一个有序集合归并-------//
        if　(c　!=　0)
            merge(a,　size　-　c　-　2　*　len,　size　-　c,　size　-　1);
        //　-------递归执行下一趟归并排序------//
        mergeSort(a,　0,　2　*　len);
    }
    public　static　void　main(String[]　args)　{
        int[]　a　=　new　int[]　{　4,　3,　6,　1,　2,　5　};
        mergeSort(a,　0,　1);
        for　(int　i　=　0;　i　<　a.length;　++i)　{
            System.out.print(a[i]　+　"　");
        }
    }
}

归并算法

定义

所谓归并排序是指将两个或两个以上有序的数列（或有序表），合并成一个仍然有序的数列（或有序表）。这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。归并排序的算法比较简单。
基本思想方法：
（1）假设已经有两个有序数列，分别存放在两个数组s，r中；并设i，j分别为指向数组的第一个单元的下标；s有n个元素，r有m个元素。
（2）再另设一个数组a，k指向该数组的第一个单元下标。
（3）算法分析（过程）：

proceduremerge(s,r,a,i,j,k);
begin
i1:=i;
j1:=j;
k1:=k;
while(i1<n)and(j1<m)do
ifs[i1]<=r[j1]then
begin
a[k]:=s[i1];
i1:=i1+1;
k:=k+1;
end
else
begin
a[k]:=r[j1];
j1:=j1+1;
k:=k+1;
end;
whilei1<=ndo
begin
a[k]:=s[i1];
i1:=i1+1;
k:=k+1;
end;
whilej1<=mdo
begin
a[k]:=r[j1];
j1:=j1+1;
k:=k+1;
end;
end;

完整的C++源代码

#include<iostream.h>
voidMerge(intr[],intr1[],ints,intm,intt){
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t){
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
if(i<=m)
while(i<=m)
r1[k++]=r[i++];
else
while(j<=t)
r1[k++]=r[j++];
for(intn=s;n<=t;n++)
r[n]=r1[n];
}
 
voidMergeSort(intr[],intr1[],ints,intt){
if(s<t){
intm=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}
voidmain(){
intr[8]={10,3,5,1,9,34,54,565},r1[8];
MergeSort(r,r1,0,7);
for(intq=0;q<8;q++)
cout<<""<<r[q];
return0；
}

归并排序的实现方法：
1.自底向上算法

#include<stdio.h>
#include<time.h>
voidMerge(int*a,intlow,intmid,inthigh){
inti=low,j=mid+1,k=0;
int*temp=(int*)malloc((high-low+1)*sizeof(int));
while(i<=mid&&j<=high)
a[i]<=a[j]?(temp[k++]=a[i++]):(temp[k++]=a[j++]);
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
memcpy(a+low,temp,(high-low+1)*sizeof(int));
free(temp);
}
voidMergeSort(int*a,intn){
intlength;
for(length=1;length<n;length*=2){
inti;
for(i=0;i+2*length-1<=n-1;i+=2*length)
Merge(a,i,i+length-1,i+2*length-1);
if(i+length<=n-1)//尚有两个子文件，其中后一个长度小于length
　Merge(a,i,i+length-1,n-1);
}
}
intmain(){
intn;
cin>>n;
int*data=new
int[n];
if(!data)
exit(1);
intk=n;
while(k--){
cin>>data[n-k-1];
}
clock_ts=clock();
MergeSort(data,n);
clock_te=clock();
k=n;
while(k--){
cout<<data[n-k-1]<<'';
}
cout<<endl;
cout<<"thealgrothemused"<<e-s<<"miliseconds."<<endl;
deletedata;
return0;
}

2.自顶向下

voidMerge(intr[],intr1[],ints,intm,intt){
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t){
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
while(i<=m)
r1[k++]=r[i++];
while(j<=t)
r1[k++]=r[j++];
for(intl=0;l<8;l++)
r[l]=r1[l];
}
 
voidMergeSort(intr[],intr1[],ints,intt){
if(s==t)
;
else{
intm=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}