数组一分为二 再利用外排的方式去merge
外排的方式:
- 两个指针 一个额外数组 谁小拷贝谁 相等默认拷贝左边
- 一个到达之后 把另外的全部拷贝进去
- 然后把数组覆盖到原来的数组
import java.util.Arrays;
public class mergesort {
static void merge(int[] a, int L, int R) {
int help[] = new int[R - L + 1];//副族数组
int m = (L + R) >> 1;
int p1 = L;//坑!!!写成了0 真的sb 每次进来都是右边 指针一
int p2 = m + 1;//指针二
int i = 0;
while (p1 <= m && p2 <= R) {
help[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];//谁小复制谁
}
while (p1 <= m) {
help[i++] = a[p1++];//把剩下的复制过去
}
while (p2 <= R) {
help[i++] = a[p2++];
}
for (i = 0; i < help.length; i++) {
a[L + i] = help[i];//每次的起始位置是L
}
}
static void mergesort(int[] a) {
if (a == null || a.length < 2) {//边界条件
return;
}
mergesort(a, 0, a.length - 1);//进入递归函数
}
static void mergesort(int[] a, int l, int r) {
if (l >= r) {
return;
}
int m = (l + r) >> 1;//坑!!!
mergesort(a, l, m);//左边递归
mergesort(a, m + 1, r);//右边递归
merge(a, l, r);//类似外排合并
}
}
