归并排序
归并排序
概述：
利用递归从数组的中间不断地分割成两部分，然后设定这两部分的起始值进行比较，小的数值放进临时数组，之后将剩余的成员放进临时数组，最后临时数组赋值给原来数组。得到从小到大排序。
场景分析：
5，3，1，2，4
利用递归从数组的中间不断地分割成两部分，
↓ ↓ ↓
5，3， |1，2，4
不断地分割成两部分，
↓ ↓ ↓
5，|3， |1， |2，4
分割成两部分，
↓ ↓ ↓
5，|3， |1， |2，|4
3，5， |1， |2，4
然后设定这两部分的起始值进行比较，
↓ ↓ ↓
3，5， |1，2，4
小的数值放进临时数组，
1，2，3，4
然后将剩余的成员放进临时数组，
1，2，3，4，5
最后临时数组赋值给原来数组， 完成从小到大排序。
1，2，3，4，5
JAVA实现：
package Sorts;
public class MergeSort {
public static void main(String[] args) {
int[] array = {5,4,3,2,1};
sort(array,0,array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + ",");
}
}
public static void sort(int[] array, int low, int high) {
int middle = (low + high)/2;
if(low < high) {
//利用递归不断的将数组分成两部分
sort(array, low, middle);
sort(array, middle + 1, high);
mergeSort(array, low, middle, high);
}
}
public static void mergeSort(int[] array,int low,int middle,int high) {
int[] temps = new int[high - low + 1];
int i = low;
int j = middle + 1;
int k = 0;
while(i <= middle && j <= high) {
//然后将两部分的起始值进行比较
if(array[i] < array[j]) {
//小的数值放进临时数组
temps[k++] = array[i++];
}else {
temps[k++] = array[j++];
}
}
//之后将这两部分剩余的成员放入临时数组
while( i <= middle ) {
temps[k++] = array[i++];
}
while( j <= high) {
temps[k++] = array[j++];
}
for (int y = 0; y < temps.length; y++) {
//最后将临时数组赋值给原来的数组，得到从小到大有序
array[y + low] = temps[y];
}
}
}
