归并排序

来自NOCOW

[编辑] 介绍

归并排序的思想很简单，我们将一个无序的序列排成有序的很麻烦，但将两个有序的序列合并成一个序列却只需要O(n)的时间就能完成。所以归并排序的做法就是将一个序列分成等长或长度差一的两个序列，对两个序列再次进行归并排序，显然只有一个元素的有序序列就是其本身，所以边界条件也很明显。

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。

[编辑] 分析

与同样是O(nlogn)的快排相比，归并排序最大的缺点就是每次合并两个序列时，都必须要一些辅助空间来完成。

[编辑] 算法实现

PASCAL:

program MergeSort;
const
 n=10;
var
 a:array[1..n] of integer;
 i:integer;
 
procedure init;
var
 i:integer;
begin
 for i:=1 to n do read(a[i]);
 readln;
end;
 
procedure merge(low,mid,high:integer);
var
 h,i,j,k:integer;
 b:array[1..n] of integer;
 
begin
 h:=low; i:=low; j:=mid+1;
 while (h<=mid) and (j<=high) do
 begin
  if (a[h]<=a[j]) then
   begin
    b[i]:=a[h]; h:=h+1;
   end
  else
   begin
    b[i]:=a[j]; j:=j+1;
   end;
  i:=i+1;
 end;
 if h>mid then
  for k:=j to high do
   begin
    b[i]:=a[k]; i:=i+1;
   end
 else
  for k:=h to mid do
   begin
    b[i]:=a[k]; i:=i+1;
   end;
  for k:=low to high do
  a[k]:=b[k];
 end;
 
procedure mergesort(low,high:integer);
var
mid:integer;
begin
 if low<high then
  begin
   mid:=(low+high) div 2;
   mergesort(low,mid); 
   mergesort(mid+1,high);
   merge(low,mid,high);
  end;
end;
 
begin
  init;
  merge(1,5,10);
  mergesort(1,10);
  for i:=1 to n do writeln(a[i]);
end.

C:

/* merges.c
 * zr95.vip@gmail.com */
 
#include <stdio.h>
#define MAX 10000
 
int D[MAX], T[MAX];
 
void merge(int *begin, int *end)
/* 归并排序左闭右开区间[begin, end) */
{
	if (end - begin > 1) {
		int *middle = begin + (end - begin) / 2;
		int *p = begin;
		int *q = middle;
		int c = 0;
		/* 分治 ——对左右半边分别进行归并排序 */
		merge(begin, middle);
		merge(middle, end);
		/* 将左右半边归并 */
		while (p < middle && q < end) {
			if (*p < *q)
			        T[c++] = *p++;
			else
			        T[c++] = *q++;
		}
		/* 当左右不等长时，不要遗漏 */
		while (p < middle)
		        T[c++] = *p++;
		while (q < end)
		        T[c++] = *q++;
		/* 复制回去 */
		while (c--)
			begin[c] = T[c];
	}
}
 
int main()
{
	int n;
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; ++i)
	        scanf("%d", &D[i]);
	merge(D, D+n);
        for (i = 0; i < n; ++i)
	        printf("%d ", D[i]);
	return 0;
}

C++:

#include <iostream>
#include <cstring>
 
using namespace std;
 
int a[1000];
 
void gbsort(int i,int j) {
 
	if (i==j) return;
	int mid=(i+j)>>1,m=mid+1,n=i;
	int* c=new int[j-i+2];
	gbsort(i,mid);
	gbsort(mid+1,j);
	for (int k=1; k<=j-i+1; k++)
		if ((a[n]<a[m] && n<=mid)||m>j) c[k]=a[n++];
			else if ((a[m]<=a[n] && m<=j)||n>mid) c[k]=a[m++];
	n=i;
	for (int k=1; k<=j-i+1; k++) a[n++]=c[k];
}
 
int main() {
 
	int n;
	scanf("%d",&n);
	for (int i=1; i<=n; i++) scanf("%d",&a[i]);
	gbsort(1,n);
	for (int i=1; i<=n; i++) printf("%d ",a[i]);
	return 0;
 
}//by ymfoi

[编辑] 算法实例

[编辑] 二路归并

例：将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表 L. 程序：

program gb;
const m=3;n=7;
type arrl1=array[1..m] of integer;
     arrl2=array[1..n] of integer;
     arrl=array[1..m+n] of integer;
var a:arrl1;
    b:arrl2;
    c:arrl;
    i,j,k,r:integer;
begin
 write('Enter l1(sorted):');
 for i:=1 to m do read(a[i]);
 write('Enter l2(sorted):');
 for i:=1 to n do read(b[i]);
 i:=1;j:=1;k:=0;
 while (i<=m) and (j<=n) do
  begin
   k:=k+1;
   if a[i]<=b[j] then begin c[k]:=a[i];i:=i+1; end
               else begin c[k]:=b[j];j:=j+1;end;
  end; 
 if i<=m then for r:=i to m do c[m+r]:=a[r];
 if j<=n then  for r:=j to n do c[n+r]:=b[r];
 writeln('Output data:');
 for i:=1 to m+n do write(c[i]:5);
 writeln;
end.

[编辑] 归并排序

程序：

program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
    i:integer;
procedure merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
 i:=l;j:=m+1;k:=l-1;
 while (i<=m)and (j<=n) do
  begin
   k:=k+1;
   if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end
                 else begin r2[k]:=r[j];j:=j+1 end
  end;
 if i<=m then
  for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
 if j<=n then
  for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procedure mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
 if s=t then r1[s]:=r[s] else
   begin
    k:=(s+t) div 2;
    mergesort(r,c,s,k);
    mergesort(r,c,k+1,t);
    merge(c,s,k,t,r1)
   end;
end;
begin
 write('Enter data:');
 for i:= 1 to maxn do
  read(a[i]);
 mergesort(a,b,1,maxn);
 for i:=1 to maxn do
  write(b[i]:9);
 writeln;
end.

归并排序是一个小作品，欢迎帮助扩充这个条目。