归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。
１、j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
２、若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
//选取r[i]和r[j]较小的存入辅助数组rf
３、如果r[i]
package MergeSort;
/** * Created by root on 3/9/16. */
public class MergeSort {
private int[] sort;
private int length;
public MergeSort(int... sort){
this.sort = sort;
length = sort.length;
}
/** * 排序 */
public void sort(){
if(length == 0){
throw new RuntimeException("没有传入任何参数!");
}else {
sort(0,length-1);
}
}
/** * * @param low 较小的一个边界 * @param high 较大的一个边界 */
public void sort(int low,int high){
int m = (low+high)/2;
if(low < high){
sort(low,m);//左边有序
sort(m+1,high);//右边有序
mergeSort(low,m,high);//左右并归
}
}
/** *将分组好的数组并归成有序数组，写入到数组sort当中。 * @param low 较小的一个边界 * @param m 中间值 * @param high 较大的一个边界 */
private void mergeSort(int low,int m,int high){
int j=m+1,i=low,k=0;
int[] temp = new int[high-low+1];
//将比较得到的有序数组放到temp数组当中
while(i<=m && j<=high){
if(sort[i]<sort[j]){
temp[k++] = sort[i++];
}else {
temp[k++] = sort[j++];
}
}
//将左边没有并归的元素加入到temp数组当中
while(i <= m){ temp[k++] = sort[i++]; }
//将右边没有并归的元素加入到temp数组当中
while(j <= high){ temp[k++] = sort[j++]; }
for(int p=0;p<temp.length;p++){ //将原来的数组替换掉。
sort[low+p] = temp[p];
}
}
/** * 打印出数组sort[]中的所有元素。 */
public void display(){
if(length == 0){
throw new RuntimeException("没有传入任何参数!");
}else{
for(int t:sort){
System.out.print(t+"\t");
}
}
}
}
测试代码：
package MergeSort;
/** * Created by root on 3/9/16. */
public class TestMergeSort {
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort(23,4,45,77,56,89,0);
System.out.println("排序前：");
mergeSort.display();
mergeSort.sort();
System.out.println("\n排序后：");
mergeSort.display();
}
}
运行结果：
