什么是归并排序
归并排序的核心思维就是分治，分而治之。将大问题分解成小问题，解决完小问题，大问题也就解决了。眼熟吗？没错，和递归的思想很相似，所以归并排序一般也是用递归实现的。
不要用人脑去递归
不要用人脑去递归
不要用人脑去递归
思考递归问题，一般确定可以把大问题拆成解题逻辑一样的小问题后，思考一下第一步拆分，和最终拆分结果一般就可以了，千万不要用人脑去思考递归的每一步是怎么样的，这样就写不出来递归的问题了。
归并排序的具体做法就是将一个大数组拆分成两个小数组，两个小数组分别排序，然后将排好序的两个小数组按照顺序合并重新成为大数组，这样大数组就是有序的了。
能否根据上面这段话列出递归公式？
f(p - r) = merge ( f(p - q), f(q+1 - r))
终止条件就是 p>=r
如果文字难以理解的话（废话！！！ （╯‵□′）╯︵┴─┴），可以看看图：
归并示意图
拆分步骤其实很好理解，就是把大数组不断对半拆分成两个小数组，重复该步骤，直到不可再拆分为止（注意，这里的拆分并不是真的把一个数组拆分成两个数组，其实是不停的划定要处理的数组范围，通过起始指针和终止指针去划定要处理的数组范围，从而达到分段处理的过程），下面重点讲一下合并的过程：
因为拆分出来的数组只能保证数组内有序，那如何讲两个数组内有序的数组合并成一个新的有序数组呢？
- 首先我们申请一个临时数组temp用于存放排序后的内容
- 我们设立两个下标（i, j）分别位于左右两个数组的起始位置（左右两个数组其实都在同一个数组内，通过start, half, end三个下标来划分左右）
- 比较两个下标所存储的数据大小，如果i比较小，则将i代表的数据放入临时数组，并将i后移一格
- 这样最后左右数组一定会有一组数据是有剩余的，将剩余数据全部加入临时数组
- 再将临时数组的值拷贝到原数组的待处理段上
有没有觉得有点难懂？（还说废话！！！ ┻━┻︵╰(‵□′)╯︵┻━┻），来！！上图（以合并步骤的第二步为例, str == start）
合并过程
理解了吗？（(๑•̀ㅂ•́)و✧）一起看下代码实现
package sort;
/**
* @author TioSun
* 归并排序
*/
public class MergeSort {
public void sort(int[] a, int n) {
mergeSort(a, 0, n - 1);
}
/**
* 归并排序数组
* @param a 待排序数据
* @param start 开始位置下标
* @param end 结束位置下标
*/
private void mergeSort(int[] a, int start, int end) {
// 不需要再拆解了
if (start >= end) {
return;
}
int half = (end + start) / 2;
// 处理左半部分数据
mergeSort(a, start, half);
// 处理右半部分数据
mergeSort(a, half + 1, end);
// 合并左右两边的数据
merge(a, start, half, end);
}
/**
* 按顺序合并左右两段数据
* @param a 待排序数据
* @param start 左半段开始下标
* @param half 左半段的结束下标
* @param end 右半段的结束下标
*/
private void merge(int[] a, int start, int half, int end) {
int i = start;
int j = half + 1;
int k = 0;
int[] temp = new int[end - start + 1];
while (i <= half && j <= end) {
// 对比左右两个拆解后的数据的大小，以从小到达的顺序移入temp数组中
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 因为会有一个半边有数据剩余，所以将有数据剩余的半边全都放进temp数组
int residueStart = i <= half ? i : j;
int residueEnd = i <= half ? half : end;
while (residueStart <= residueEnd) {
temp[k++] = a[residueStart++];
}
// 将排好序的数据放入原数组中
for (int q = 0; q < k; q++) {
a[start + q] = temp[q];
}
}
}
好理解吧？o(￣▽￣)ｄ
网友评论