归并排序

综述

归并排序是建立在归并操作上的一种有效的排序算法。这个算法是分治法的一个典型的应用。

1.有序数组合并

有序数组合并非常简单，只要比较两个数组中最小的数，谁小就取谁。然后把取了的数删除，继续比较。如果一个数组为空，则取另一个数组的元素。 这个方法时间复杂度为O（n）

public void MemeryArray(int[] a,int n,int[] b,int m,int c[]){ int i,j,k; i=j=k=0; while(i<n&&j<m){ if(a[i]>b[j]){ c[k++]=b[j++]; }else{ c[k++]=a[i++]; } } while(i<n){ c[k++]=a[i++]; } while(j<m){ c[k++]=b[j++]; } }

2.归并排序

归并排序就是建立在有序数组合并的基础上。 把数组分成两组A，B。A，B又分成两组C，D，E，F。 直到分出来的小组只有一个数据，可以认为小组内达到有序，然后再合并相邻的小组就行了。 先递归分解数列，在合并数列，就完成了归并排序。

public class MergeSort { public 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); } public static void mergeSort(int[] a,int s,int len){ int size=a.length; int mid=size/(len<<1);//size/2len int c=size&((len<<1)-1);//对2len取余 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] + "　"); } } }

总结

归并排序是一种稳定的算法，其复杂度为O（nlogn）。