标签（空格分隔）： java
本次我们来谈一下排序算法中的并归排序算法
首先我们来了解一下归并排序的思想：分治法；
分治法的思想是，当我们求解一个大问题需要很多的时间，并且方式很难实现，我们发现，如果将这个如果将这个大问题分解成若干个小问题，则问题就变得简单很多，这些小问题求解的同时，原问题也得以求解，我们将一个大问题逐步分解成若干个小问题求解的思想，就是分治法，同时也是递归思想。
归并排序算法就是利用了这种思想。
首先对于一个大的数据集，我们不好排序，我们将这个数据集一分为二，分成两个小的数据集，我们假设，如果这两个数据集排序完成，剩下的工作就是讲这两个有序的数据集合并成一个有序的的数据集，
于是我们的当下任务可以分成两个，首先第一个是，排序这个两个小的数据集，然后的任务是，将这两个小的数据集整合到一个有序的数据集。
解决第一个任务：拆分
如果原来的数据集很大，我们拆分成两个数据集的时候，发现，还是不好排序，怎么办，答案很简单，说明它还不够小，于是，我们对着两个数据集，也采用相同的做法，在拆分，以此类推，一直到我们的拆分的数据集只有一个数据为止，这个时候，我们发现，对于只有一个数据元素的数据集，它的顺序也就已经确定了，我们的排序也就完成了。也就是说只要我们对数据不停的拆分，最后将每一个数据集拆分成只有一个数据元素的时候，其排序过程其实就已经完成了。
解决第二个任务：合并
经过上一个步骤，我们就得到了两个有序的数据集合，然后，我们的任务就是将这两个有序的数据集合并成一个有序的数据集合。这里我们举一个例子，桌子上有两副有序的牌，我们要将他们合并成一副有序的牌，我们该怎么做呢，很简单，假设两副陪得顺序都是从小到大排放，小的在上面，首先，我们分别从两副牌的顶端，各取一个，然后比较谁打谁小，将小的放到手中，大的不动，然后在从两副牌的顶端在取两张牌，再比，以此类推，知道一副牌比完，或者两副牌都同时比完，如果其中的一副牌先比完，则将剩下的牌就不用比了，直接放到手中就行了，这时，手中的牌就是合并好的有序的牌了。
好了原理我们说的差不多了，然后我们来说一下如何用代码实现呢？
通过上面分析，我们发现，第一个任务似乎不是很难，我们先完成拆分。
public static void mergerInside(int[] arr, int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
//对左边数据集在拆分
mergerInside(arr, start, middle);
//对右边数据集在拆分
mergerInside(arr, middle + 1，end);
//合并左右数据集
merger(arr, start, middle, end);
}
}
通过上面的分析我们知道，这个方法是一个递归的过场，也就是在拆分完成到最后，左右两边的数据集都是已经排好序的，然后我们进行合并，合并的结果也是一个有序的数据集。这样，我们的递推关系就可以正确进行下去了。
其实，才分并不是最难的部分，我们的关键重点是合并。
public static void merger(int[] arr, int start, int middle, int end) {
//左边数组的长度
int left_len = middle - start + 1;
//右边数组的长度
int right_len = end - middle;
//左边数组
int[] leftArr = new int[left_len];
//右边数组
int[] rightArr = new int[right_len];
int i = 0;
int j = 0;
//为左边数据赋值
for (; i < left_len; i++) {
leftArr[i] = arr[start + i];
}
//为右边数组赋值
for (; j < right_len; j++) {
rightArr[j] = arr[middle + 1 + j];
}
i = 0;
j = 0;
int k = start;
//从左右两边的顶端分别取一个数据，然后比较，将小的放到第一个位置
while (i < left_len && j < right_len) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
//右边的数据用完了，然后直接将左边的数据复制到数组中
if (i < left_len) {
arr[k++] = leftArr[i++];
}
//左边数据用完了，然后直接将右边的数组复制到数组中
if (j < right_len) {
arr[k++] = rightArr[j++];
}
}
好了合并也分析完了，我们来看一下总体优化下一下，我们看到这里我们使用Java写的，在合并的时候创建了多个数组。这显然不合适。
public class Demo {
public static void main(String[] args) {
int[] arr = { 3, 7, 5, 8, 9, 10, 4, 2, 13, 15 };
//排序数组
mergerSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
public static void mergerSort(int[] arr) {
//建立好两个大数组，避免多次创建数组
int[] leftArr = new int[arr.length];
int[] rightArr = new int[arr.length];
mergerInside(arr, 0, arr.length - 1,leftArr,rightArr);
}
public static void mergerInside(int[] arr, int start, int end,int[] leftArr,int[] rightArr) {
if (start < end) {
int middle = (start + end) / 2;
mergerInside(arr, start, middle,leftArr,rightArr);
mergerInside(arr, middle + 1, end,leftArr,rightArr);
merger(arr, start, middle, end,leftArr,rightArr);
}
}
public static void merger(int[] arr, int start, int middle, int end,int[] leftArr,int [] rightArr) {
int left_len = middle - start + 1;
int right_len = end - middle;
int i = 0;
int j = 0;
for (; i < left_len; i++) {
leftArr[i] = arr[start + i];
}
for (; j < right_len; j++) {
rightArr[j] = arr[middle + 1 + j];
}
i = 0;
j = 0;
int k = start;
while (i < left_len && j < right_len) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
if (i < left_len) {
arr[k++] = leftArr[i++];
}
if (j < right_len) {
arr[k++] = rightArr[j++];
}
}
}
网友评论