归并排序与时间复杂度
--------------------------
讲归并排序之前，先讲讲什么事递归？递归就是自己调用自己。
比如 f（x）= x^2+ f(x - 1)且f（0）=0；
这个就是递归，比如你要求f(5)就必须先求出f(4)又得求出f(3)不断的递归下去直到f(0),这里要是没有f（0）=0，那么它就会一直递归下去直到负无穷。这是不允许的，所以f（0）=0是递归的基准情形。
递归的基本法则：（1）必须有基准情形
（2）不断推进 每一次递归都必须向基准情形推进
--------------------------------
（一）什么是归并排序？归并排序就是就是把待排序的数据分成几个子序列，对子序列进行排序后，把有序的子序列合并成整体有序的序列。
（二）递归排序的基本过程：比如现在要排序int a[] = {72,6,57,88,60,42,83,73,48,85};
那么首先把数组分成两个子序列a1[]= {72,6,57,88,60}; a2 []={42,83,73,48,85};
接着对a1，a2再分子序列，a11[] = {72,6,57} a12[] = {88,60};
a21[] = {42,83,73} a22[] = {48,85};
接着对a11，a21再分子序列a111[] = {72,6} a211= {42,83} 这时候不在会发生递归，接着就是排序
（三）代码如下：
public class GuiBing {
public static void main (String agrs[]){
int a[] = {72,6,57,88,60,42,83,73,48,85};
guibing_sort(a,0,a.length-1);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+",");
}
public static void guibing_sort(int s[],int low,int high){
int mid = (low + high)/2;
if(low < high){
guibing_sort(s,low,mid);//递归
guibing_sort(s,mid + 1,high);
merge(s,low,mid,high);
}
}
public static void merge(int s[],int low,int mid,int high){//最小的执行单元是2
// 0 0 1
int temp[] = new int[high - low + 1];//定义一个临时数组用来存放排好的数据
int i = low;
int j = mid +1;
int k = 0;
// 把较小的数先移到新数组中
while(i <= mid && j <= high){
if(s[i]< s[j]){
temp[k++] = s[i++];
}else{
temp[k++] = s[j++];}
}
// 把左边剩余的数移入数组
while(i <= mid){
temp[k++] = s[i++];
}
// 把右边边剩余的数移入数组
while(j <= high){
temp[k++] = s[j++];
}
// 把新数组中的数覆盖s数组
for (int k2 = 0; k2 < temp.length; k2++) {
s[k2 + low] = temp[k2];
}
}
（四）时间复杂度：归并排序的时间复杂度为O（nlogn）