归并排序(一)
上两篇博客介绍了选择排序插入排序和希尔排序 这次以我的理解来介绍一下归并排序 在百科上面看到的概念:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
二路归并就是把2个有序的序列归并到一起,形成一个有序的序列
假如 a =[ 2,4,5,6] b=[1,3,6,9,10] 归并的过程就是先定义一个数组c c.length = a.length + b.length int i,j; i=j=0; //a,b的索引 for(int k=0;k<c.length;k++){ if(i>a.length-1) c[k]=b[j++] //当a的元素全部插入到c中是 直接按顺序把b中的元素插入到c中 else if(j>b.length-1) c[k]=a[i++] //当b的元素全部插入到c中是 直接按顺序把a中的元素插入到c中 else if(a[i]<b[j]) c[k]=a[i++] //a,b中对应值小的插入到c中 else c[k]=b[j++] //a,b中对应值小的插入到c中 }
归并排序其实是对一个数组采用递归的形式来进行二路归并(下面我们将详细介绍),为了避免额外的开销,我们采用原地归并
下面我们来介绍一下原地归并,由于每次归并我们都要申请而外的空间,来共二个序列来归并,我们想能不能这样,直接定义一个静态数组 每次归并前我们把需要递归的元素复制到这个静态数组里面
下面我们来介绍归并排序的思路;
public static void merge(Comparable [] a,int lo,int mid,int hi){ int i = lo; int j = mid + 1; for(int k=lo;k<=hi;k++) b[k] = a[k]; for(int k=lo;k<=hi;k++){ if(i>mid) a[k] = b[j++]; else if(j>hi) a[k] = b[i++]; else if(less(b[i],b[j])) a[k] = b[i++]; else a[k] = b[j++]; } }
这是我们原地归并的代码 要注意hi = length-1 mid = lo + (hi-lo)/2
我们先给出归并排序的代码,供读者思考(用递归的思想)
public static void sort(Comparable [] a,int lo,int hi){ if(lo>=hi) return; int mid = lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); } public static void sort(Comparable [] a){ b = new Comparable[a.length]; sort(a,0,a.length-1); }
下面给出图供大家理解
实际上就是递归到长度为1时返回到上一次 将2个长度为1的归并起来......
全代码: public class MergeSort { public static boolean less(Comparable a,Comparable b){ return a.compareTo(b)<0; } private static Comparable [] b; public static void merge(Comparable [] a,int lo,int mid,int hi){ int i = lo; int j = mid + 1; for(int k=lo;k<=hi;k++) b[k] = a[k]; for(int k=lo;k<=hi;k++){ if(i>mid) a[k] = b[j++]; else if(j>hi) a[k] = b[i++]; else if(less(b[i],b[j])) a[k] = b[i++]; else a[k] = b[j++]; } } public static void show(Comparable [] a){ for(int i=0;i<a.length;i++) System.out.printf("%f ",a[i]); System.out.println(); } public static void sort(Comparable [] a,int lo,int hi){ if(lo>=hi) return; int mid = lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); } public static void sort(Comparable [] a){ b = new Comparable[a.length]; sort(a,0,a.length-1); } public static void main(String [] args){ Double [] test = new Double[10]; for(int i=0;i<10;i++) test[i] = (Math.random()*15); show(test); sort(test); show(test); } }