毕业人士的时间大部分花在工作上， 对学生时代的算法训练就逐渐忘记了。但对基本的算法还是应该知道的。
归并排序的思路（分而治之）：
- 划分问题：将数组分为数量相等的两半
- 递归求解：把两半元素分别排序
- 合并问题：将两个有序子数组合并成一个
public class MergeSort {
public void mergeSort(int[] A, final int i, final int j, int[] B) {
if (i >= j) {
// 递归边界：此时数组中只有一个元素，无须排序
return;
}
int m = i + (j - i) / 2;
mergeSort(A, i, m, B);
mergeSort(A, m + 1, j, B);
int x = i;
int y = m + 1;
int index = i;
while (x <= m || y <= j) {
if (x > m || (y <= j && A[y] <= A[x])) {
B[index++] = A[y++];
} else {
B[index++] = A[x++];
}
}
// 忘记的代码
for (int k = i; k <= j; k++) {
A[k] = B[k];
}
}
public static void main(String[] args) {
int len = 20;
int[] A = new int[len];
int[] B = new int[len];
for (int i = 0; i < len; i++) {
A[i] = ThreadLocalRandom.current().nextInt(100);
}
System.out.println(Arrays.toString(A));
MergeSort sort = new MergeSort();
sort.mergeSort(A, 0, len - 1, B);
System.out.println(Arrays.toString(A));
System.out.println(Arrays.toString(B));
}
}
一开始没看书，自己写，忽略了有注释的代码。B作为辅助空间，只是为了第三部归并的时候使用。
参考资料：《算法竞赛入门经典》
