合并排序
合并排序合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
复杂度时间O(nlogn)
空间O(n)
与快速排序类似
java源码import org.rut.util.algorithm.SortUtil;
public class MergeSort implements SortUtil.Sort{
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
private void mergeSort(int[] data,int[] temp,int l,int r){
int mid=(l+r)/2;
if(l==r) return ;
mergeSort(data,temp,l,mid);
mergeSort(data,temp,mid+1,r);
for(int i=l;i<=r;i++){
temp[i]=data[i];
}
int i1=l;
int i2=mid+1;
for(int cur=l;cur<=r;cur++){
if(i1==mid+1)
data[cur]=temp[i2++];
else if(i2>r)
data[cur]=temp[i1++];
else if(temp[i1]<temp[i2])
data[cur]=temp[i1++];
else
data[cur]=temp[i2++];
}
}
}
//改进后的归并排序:
import org.rut.util.algorithm.SortUtil;
public class ImprovedMergeSort implements SortUtil.Sort {
private static final int THRESHOLD = 10;
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
private void mergeSort(int[] data, int[] temp, int l, int r) {
int i, j, k;
int mid = (l + r) / 2;
if (l == r)
return;
if ((mid - l) >= THRESHOLD)
mergeSort(data, temp, l, mid);
else
insertSort(data, l, mid - l + 1);
if ((r - mid) > THRESHOLD)
mergeSort(data, temp, mid + 1, r);
else
insertSort(data, mid + 1, r - mid);
for (i = l; i <= mid; i++) {
temp[i] = data[i];
}
for (j = 1; j <= r - mid; j++) {
temp[r - j + 1] = data[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l, j = r, k = l; k <= r; k++) {
if (a < b) {
data[k] = temp[i++];
a = temp[i];
} else {
data[k] = temp[j--];
b = temp[j];
} } }
private void insertSort(int[] data, int start, int len) {
for(int i=start+1;i<start+len;i++){
for(int j=i;(j>start) && data[j]<data[j-1];j--){
SortUtil.swap(data,j,j-1);
} } } }
C++源码#include<iostream.h>
template<class T>void MergeSort(T a[],int left,int right);
template<class T>void Merge(T c[],T d[],int l,int m,int r);
template<class T>void Copy(T a[],T b[],int l,int r);
void main()
{
int const n(5);
int a[n];
cout<<"Input "<< n <<" numbers please:";
for(int i=0;i<n;i++)
cin>>a[i];
//for(int j=0;j<n;j++)
//b[j]=a[j];
MergeSort(a,0,n-1);
cout<<"The sorted array is"<<endl;
for(i=0;i<n;i++)
cout<<a[i];
cout<<endl;
}
template<class T>
void MergeSort(T a[],int left,int right)
{
if(left < right)
{
int i = (right + left)/2;
T *b=new T[];
MergeSort(a, left, i);
MergeSort(a, i+1, right);
Merge(a, b, left, i, right);
Copy(a,b,left,right);
}
}
template<class T>
void Merge(T c[],T d[], int l, int m, int r)
{
int i = l, j = m+1, k = l;
while(i <= m && j <= r)
{
if(c[i] <= c[j])d[k++]=c[i++];
else d[k++]=c[j++];
}
if(i > m)
{
for(int q = j; q <= r; q ++)
d[k++] = c[q];
}
else
for(int q = i; q <= m; q ++)
d[k++] = c[q];
}
template<class T>
void Copy(T a[],T b[],int l,int r)
{
for(int i=l;i<=r;i++)
a[i]=b[i];
}