排序算法之归并排序java实现

1、归并排序算法思想

归并排序主要是二路归并排序。

二路归并排序的基本思想是：设数组a中存放了n个数据元素，初始时把它们看成是n个长度为1的有序子数组，然后从第一个子数组开始，把相临的子数组两两合并，得到n/2个长度为2的新的有序子数组（当n为奇数时最后一个新的子数组长度为1）；对这些新的子数组再两两合并；如此重复，直到得到一个长度为n的有序数组为止。
二路归并排序过程如下图所示（图片来自百度图片）

归并排序是高效算法中唯一稳定的排序算法。多用于外部排序，较少用于内部排序。

2、复杂度分析

对于n个元素的数组，将这n个元素看作叶子节点，将两两归并生成的子集看作它们的父节点，则归并过程对应于由叶子节点向根节点生成的一棵二叉树的过程。所以，归并趟数约等于二叉树的高度减1，即，每趟归并排序元素比较次数都约为n/2，元素移动的次数为2n（临时顺序表的元素复制到原顺序表中元素的移动次数为n）。因此，二路归并排序的时间复杂度为。而二路归并排序使用了n个临时内存单元存放元素，所以，二路归并排序算法空间复杂度为O(n)。

3、归并排序java实现

package sort;

public class MergeSort {

public static void main(String[] args) {

int[] a = {18, 45, 36, 30, 92, 72, 25};
mergeSort(a,0,a.length-1);
for(int i=0;i<a.length-1;i++){
System.out.print(a[i]+" ");
}
}

//归并
public static void merge(int[] a, int start, int mid, int end){
int[] temp = new int[a.length];
int i = start, j = mid+1, k = start;
while(i!=mid+1 && j!=end+1){
if(a[i]<a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}

while(i!=mid+1){
temp[k++] = a[i++];
}

while(j!=end+1){
temp[k++] = a[j++];
}

for(i=start; i<=end; i++)
a[i] = temp[i];
}

//归并排序
public static void mergeSort(int[] a, int start, int end){
if(start < end){
int mid = (start+end)/2;
mergeSort(a, start, mid);//左边排序
mergeSort(a, mid+1, end);//右边排序
merge(a, start, mid, end);
}
}
}

输出：18 25 30 36 45 72