归并排序

归并排序

　　归并排序，故名思议有分而治之的思想，就是将一个待排序的数组分成多组，分组方法采用每一次两两分组的方法，对分好组的数据进行组间重排大小，将排好序的数组元素放入一个临时数组中存放，当排序结束后将得到的排好序的序列覆盖原数组序列即可。

java代码如下：

/**
 * 归并排序:关键在于并，分采用二分法，每次从中间分组，采用递归。
 * 归并的过程中将两个分好组的序列依次排好序以后合并
 * @author 1
 *
 */
public class MergeSort {
	
	public static void mergeSort(int [] arr, int low, int high) {
		int mid=(low+high)/2;
		
		if(low<high) {
			mergeSort(arr,low,mid);
			mergeSort(arr,mid+1,high);
			merge(arr, low, mid, high);
		}
	}
	
	private static void merge(int [] arr, int low, int mid, int high) {
		int []  temp=new int [high-low+1];
		int i=low;
		int j=mid+1;
		int k=0;
		//比较两个分组中数的大小，将较小的数放在合并后数组的前边
		while(i<=mid && j<=high) {
			if(arr[i]<arr[j]) {
				temp[k]=arr[i];
				k++;
				i++;
			}else {
				temp[k]=arr[j];
				k++;
				j++;
			}
		}
		//将前一个分组中剩余的数全部加到合并后的数组后面
		while(i<=mid) {
			temp[k]=arr[i];
			k++;
			i++;
		}
		//将后一个分组中剩余的数全部加到合并后的数组后面
		while(j<=high) {
			temp[k]=arr[j];
			k++;
			j++;
		}
		//将合并后的数组的值覆盖掉原数组中对应位置的值
		for(int k2=0;k2<temp.length;k2++) {
			arr[k2+low]=temp[k2];
		}
	}
	
	public static void main(String[] args) {
		int [] arr= {6,5,4,3,2,1};
		mergeSort(arr, 0, arr.length-1);
		for(int i:arr) {
			System.out.print(i+" ");
		}
	}
}
由以上算法可知，该算法的时间复杂度为nlogn,但是空间复杂度较大，因为每一次归并都需要一个临时数组来存排好序的数。