归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。
在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。
每一趟归并的时间复杂度为 O(n)
在插入排序，选择排序，快速排序，归并排序这几种排序中，要求内存量最大的是归并排序。
F. 归并排序
{a为序列表，tmp为辅助数组}
procedure merge(var a:listtype; p,q,r:integer);
{将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]}
var I,j,t:integer;
tmp:listtype;
begin
t:=p;i:=p;j:=q+1;{t为tmp指针，I,j分别为左右子序列的指针}
while (t<=r) do begin
if (i<=q){左序列有剩余} and ((j>r) or (a<=a[j])) {满足取左边序列当前元素的要求}
then begin
tmp[t]:=a; inc(i);
end
else begin
tmp[t]:=a[j];inc(j);
end;
inc(t);
end;
for i:=p to r do a:=tmp;
end;{merge}
procedure merge_sort(var a:listtype; p,r: integer); {合并排序a[p..r]}
var q:integer;
begin
if p<>r then begin
q:=(p+r-1) div 2;
merge_sort (a,p,q);
merge_sort (a,q+1,r);
merge (a,p,q,r);
end;
end;
{main}
begin
merge_sort(a,1,n);
end.
C#的实现:
class MergeSort
{
public MergeSort()
{ }
public int[] Sort(int[] data)
{
Merge_Sort(data, 0, data.Length - 1);
return data;
}
private void Merge_Sort(int[] data, int first, int last)
{
int mid = 0;
if (first < last)
{
mid = (first + last) / 2;
Merge_Sort(data, first, mid);
Merge_Sort(data, mid + 1, last);
Merge(data, first, mid, last);
}
}
private void Merge(int[] data, int first, int mid, int last)
{
int[] temp = new int[last-first+1];
int begin1, begin2, end1, end2;
int index = 0;
begin1 = first;
begin2 = mid + 1;//这里很重要,如果换成begin2 = mid ;end1 = mid -1;结果将完全不对;
end1 = mid;
end2 = last;
while ((begin1 <= end1) && (begin2 <= end2))
{
if (data[begin1] > data[begin2])
temp[index] = data[begin1++];
else
temp[index] = data[begin2++];
index++;
}
while (begin1 <= end1)
temp[index++] = data[begin1++];
while (begin2 <= end2)
temp[index++] = data[begin2++];
for (int i =0,k = first; k <= last; k++,i++)
data[k] = temp[i];
}
}
我的归并排序代码注：ar为待排序数组，tar为与ar等大的临时数组。mg_sort会把ar数组中下标在[f..t-1]之内的元素排序。
void mg_sort(int f,int t,int *ar,int *tar) {
if(f+1<t) {
int m,i,j,k;
m=(f+t)/2;
memcpy(tar+f,ar+f,(t-f)*sizeof(int));
mg_sort(f,m,tar,ar);
mg_sort(m,t,tar,ar);
i=f;
j=m;
k=f;
while(i<m && j<t)
ar[k++]= tar[i]>=tar[j] ? tar[i++]:tar[j++] ;
while(i<m)
ar[k++]=tar[i++];
while(j<t)
ar[k++]=tar[j++];
}
}
C语言完整实现
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h >
void merge(int array[], int p, int q, int r)
{
int* temp = new int [r-p+1]; //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
int m=p;
int n=q+1;
int k = 0;
while((m<=q)&&( n<=r)) //比较两个下标所指向的元素，选择相对小的元素放入到合并空间，并移动下标到下一位置
{
if(array[m]<array[n])
{
temp[k] = array[m];
m++;
}
else
{
temp[k] = array[n];
n++;
}
k++;
}
while(m<=q) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
{
temp[k] = array[m];
k++;
m++;
}
while(n<=r) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
{
temp[k] = array[n];
k++;
n++;
}
for (int i = 0; i < (r - p +1); i++) //将排序好的序列拷贝回数组中
{
array[p+i] = temp[i];
}
}
void mergesort(int A[],int p,int r)
{
if (p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
int main()
{
int A[9]={9,3,6,1,4,7,2,8,5};
mergesort(A,0,8);
for (int i = 0; i < 9; i++) //打印数组
{
cout<<A[i] ;
}
return 1;
}