复杂度nlog(n)之归并排序

1.简单的介绍

平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度
nlog(n)	nlog(n)	nlog(n)	O(1)

2.核心的merge函数

/**
 * 将分割开的两个数组合并，[start,middle]和[middle+1,end]这两个数组合并成为一个新的排序数组
 * @param array
 * @param start
 * @param middle
 * @param end
 */
public static void merge(int[] array,int start,int middle,int end)
    {
int [] temp=new int[end-start+1];
int k=0;
int start1=start;
int end1=middle;
int start2=middle+1;
int end2=end;
while(start1<=end1&&start2<=end2)
        {
if(array[start1]<=array[start2])
            {
                temp[k++]=array[start1++];
            }else
            {
                temp[k++]=array[start2++];
            }
        }
while(start1<=end1)
        {
            temp[k++]=array[start1++];
        }
while(start2<=end2)
        {
            temp[k++]=array[start2++];
        }
for(int i=0;i<k;i++)
        {
            array[start+i]=temp[i];
        }
    }

上面函数就是数组被递归分割后的两个数组，将他们重新拼成一个排序数组。

3.完整的代码

    public static void mergesort(int[] array,int start,int end)
 {
if(start<end)
 {
int middle=(start+end)/2;
            mergesort(array, start, middle);
            mergesort(array, middle+1, end);
merge(array, start, middle, end);
        }
    }

归并算法大致就是利用不停地递归不停地将数组一分为二，知道他们被分成一个一个的。然后再回溯不停地合并，最终将他们变成一个排序数组。