排序算法之归并排序

####简介
归并算法的核心思想就是分治，然后合并结果集。
比如一个数组，最开始一分为二，然后对左右两边的数据再进行拆分，以此类推，直到拆分到每组数组里只有一个数据，此时就进行合并，这样一来，最后合并起来的数组就是有序的了。
####实现
也许上面讲的还是有点不太明白，那么接下来就以一组数据为例吧。在实现该算法之前，首要要知道如何将两个有序数组合并？因为该算法的思想就包含了两个有序数组的合并部分。
两个有序数组的合并，我们可以采用直接插入排序的思想，实现代码如下：
```java
private void merge(int[] arr1, int[] arr2) {
		int[] temp = new int[arr1.length + arr2.length];
		int i = 0;
		int j = 0;
		int k = 0;
		while (i < arr1.length && j < arr2.length) {
			if (arr[i] < arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}
		}

while (i < arr1.length)
			temp[k++] = arr[i++];
		while (j < arr2.length)
			temp[k++] = arr[j++];
	}
```
有了以上合并的基础，接下来就是递归分治 + 合并来实现了，整个代码如下：
```java
public class MergeSort {

private int[] arr;

private void sort(int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			sort(left, mid);
			sort(mid + 1, right);
			merge(left, mid, right);
		}
	}

private void merge(int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int i = left;
		int j = mid + 1;
		int k = 0;
		while (i <= mid && j <= right) {
			if (arr[i] < arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}
		}

while (i <= mid)
			temp[k++] = arr[i++];
		while (j <= right)
			temp[k++] = arr[j++];
		int m = 0;
		for (int n = left; n <= right; n++) {
			arr[n] = temp[m++];
		}
	}

private void init() {
		Random random = new Random();
		arr = new int[10];
		for (int i = 0; i < arr.length; i++)
			arr[i] = random.nextInt(100);
	}

private void print() {
		for (int a : arr)
			System.out.print(a + " ");
		System.out.println();
	}

public static void main(String[] args) {
		MergeSort ms = new MergeSort();
		ms.init();
		System.out.println("排序之前：");
		ms.print();
		ms.sort(0, 9);
		System.out.println("排序之后：");
		ms.print();
	}
}
```
代码清晰明了，基本上不用注释了。。。

排序算法之归并排序

发表评论：