归并排序
基本思想：将初始序列中的n个对象，看成n个长度为1的有序子序列，先做两两归并，得到int(n/2）个长度为2的归并项（如果n为奇数，则最后一个有序子序列为1）；在做两两归并，重复直到最后得到一个长度为n的有序序列。
图解：
代码实现：
public class MergeSort{
//归并排序(升序)
public static void mergeSort(int[] sorted,int left,int right){
int min = (left + right) / 2;
if(left < right){
//将序列分为左右两个子序列
//再分别对左右两个子序列再分为左右两个子序列
mergerSort(sorted,left,min);
mergerSort(sorted,min + 1,right);
//排序并合并
int[] temp = new int[right - left + 1]
int i = left;
int j = min + 1;
int k = 0;
while(i <= min && j <= right){
if(sorted[i] < sorted[j]){
temp[k++] = sorted[i++];
}else{
temp[k++] = sorted[j++];
}
}
//将左边剩余的数据放入新数组
while(i <= min){
temp[k++] = sorted[i++];
}
//将右边剩余的数据放入新数组
while(j <= right){
temp[k++] = sorted[j++];
}
//排好序的新数组覆盖原数组
for(int n = 0;n < temp.length;n++){
sorted[n + left] = temp[n];
}
}
}
//归并排序结束
//测试
public static void main(String[] args) {
int[] sort = new int[9];
sort[0] = 2;
sort[1] = 88;
sort[2] = 1;
sort[3] = 8;
sort[4] = 7;
sort[5] = 38;
sort[6] = 28;
sort[7] = 72;
sort[8] = 76;
System.out.println("Before Sort:");
System.out.println(Arrays.toString(sort));
MergeSort.mergerSort(sort,0,sort.length - 1);
System.out.println("After Sort:");
System.out.print(Arrays.toString(sort));
}
}