本文共 3351 字，大约阅读时间需要 11 分钟。

目录

一、二路归并实现

递归实现，栈空间：O(logn)、堆空间：O(nlogn)

public static void mergeSort1(int[] arr) {  // 多做一层包装，简化用户输入		mergeSort1(arr, 0, arr.length-1);	}	public static void mergeSort1(int[] arr, int left, int right) {		int mid = (right+left) / 2;		if (left < right) {			mergeSort1(arr, left, mid);			mergeSort1(arr, mid+1, right);			merge1(arr, left, right, mid);		} 	}	public static void merge1(int[] arr, int left, int right, int mid) {		int[] temp = new int[right-left+1];		int i = left;		int j = mid+1;		int k = 0;		for (; i<=mid && j<=right; k++) {			if (arr[i] < arr[j]) {				temp[k] = arr[i];				i = i + 1;			} else {				temp[k] = arr[j];				j = j + 1;			}		}		// 两部分中哪一部分多出一些元素，就把该部分的所有元素直接加入temp数组		while (i <= mid) {			temp[k++] = arr[i++];		}		while (j <= right) {			temp[k++] = arr[j++];		}				// 将排好序的temp数组的所有元素写入原数组的指定位置		for (int l=0; l

二、二路归并的一点优化

上面的代码中因为每一趟都要新建一个数组temp来临时存放已经处理好的相对有序的数组，所以使用的堆空间为O(nlogn)。这里我们将使用的空间降到O(n)，也就是整个过程只新建一个大小为n的数组。

递归实现，栈空间：O(logn)、堆空间：O(n)

public static void mergeSort2(int[] arr) {		int[] temp = new int[arr.length];		mergeSort2(arr, temp, 0, arr.length-1);	}	public static void mergeSort2(int[] arr, int[] temp, int left, int right) {		int mid = (right+left) / 2;		if (left < right) {			mergeSort2(arr, temp, left, mid);			mergeSort2(arr, temp, mid+1, right);			merge2(arr, temp, left, right, mid);		} 	}	public static void merge2(int[] arr, int[] temp, int left, int right, int mid) {		int i = left;		int j = mid+1;		int k = left;		for (; i<=mid && j<=right; k++) {			if (arr[i] < arr[j]) {				temp[k] = arr[i];				i = i + 1;			} else {				temp[k] = arr[j];				j = j + 1;			}		}		// 两部分中哪一部分多出一些元素，就把该部分的所有元素直接加入temp数组		while (i <= mid) {			temp[k++] = arr[i++];		}		while (j <= right) {			temp[k++] = arr[j++];		}				// 将排好序的temp数组的所有元素写入原数组的指定位置		for (int l=left; l<=right; l++) {			arr[l] = temp[l];		}	}

三、原地归并实现

我们再继续将堆空间的复杂度降为O(1)

递归实现，栈空间：O(logn)、堆空间：O(1)

public static void mergeSort3(int[] arr) {		//int[] temp = new int[arr.length];		mergeSort3(arr, 0, arr.length-1);	}	public static void mergeSort3(int[] arr, int left, int right) {		int mid = (right+left) / 2;		if (left < right) {			mergeSort3(arr, left, mid);			mergeSort3(arr, mid+1, right);			merge3(arr, left, mid, right);		} 	}	public static void merge3(int[] arr, int left, int mid, int right) {		int i = left;		int j=mid+1;		/*		while (i

四、二路归并的非递归实现

非递归实现，栈空间：O(1)、堆空间：O(nlogn)

public static void mergeSort4(int[] arr) {		int len = arr.length;		int k = 1;				while (k < len) {			mergePass(arr, k, len);			k *= 2;		}	}	public static void mergePass(int[] arr, int k, int n) {		int i = 0;		int j;				//从前往后，把2个（一对）长度为k的子序列合并为1个		while (i < n-2*k+1) {			merge(arr, i, i+k-1, i+2*k-1);			i += 2*k;		}				//这段代码保证了，将那些“落单的”长度不足两两merge的部分和前面merge起来		if (i < n-k) {			merge(arr, i, i+k-1, n-1);		}	}	public static void merge(int[] arr, int low, int mid, int high) {		//temp数组用于暂存合并的结果		int[] temp = new int[high-low+1];		//左半边的指针		int i = low;		//后半边的指针		int j = mid+1;		//合并后数组的指针		int k = 0;				//将记录从小到大（有序地）放进temp数组		for (; i<=mid && j<=high; k++) {			if (arr[i] <= arr[j]) {				temp[k] = arr[i++];			} else {				temp[k] = arr[j++];			}		}		//接下来的两个while循环是为了将一边剩余的（比另一边多出来的个数）放到temp数组中		while (i <= mid) {			temp[k++] = arr[i++];		}		while (j <= high) {			temp[k++] = arr[j++];		}				//将temp数组中的元素写入原数组中的对应位置		for (int l=0; l

五、在归并排序中使用直接插入排序

待续

转载地址：http://mbnii.baihongyu.com/