1. 思想
将数组分割成一个一个有序的子数组,然后将子数组两两合并起来,形成一个新的有序数组
2. 算法
- 先写一个函数用于分割数组,直到数组不可再分
- 然后开始回溯合并子数组
- 合并时先将左子数组和右子数组分别保存出来
然后遍历整个左子数组和右子数组,判断四种情况:
- 左子数组遍历完,右子数组未遍历完
- 右子数组遍历完,左子数组未遍历完
- 左子数组头元素小于右子数组头元素,就将左子数组头元素放入外部数组
- 右子数组头元素小于等于左子数组头元素,就将右子数组头元素放入外部数组
3. 代码
参考视频:
private static void mergeSort(int[] array, int left, int right) {
// 递归跳出条件
if (left >= right) {
return;
}
int middle = (left + right) >> 1;
mergeSort(array, left, middle);
mergeSort(array, middle + 1, right);
merge(array, left, middle, right);
}
private static void merge(int[] array, int l, int m, int r) {
int[] leftArray = new int[m - l + 1];
int[] rightArray = new int[r - m];
int leftHead = l;
int rightHead = m + 1;
// 填充左子数组
for (int i = leftHead; i <= m; i++) {
leftArray[i - leftHead] = array[i];
}
// 填充右子数组
for (int i = rightHead; i <= r; i++) {
rightArray[i - rightHead] = array[i];
}
// 注意要先判断子数组是否遍历完的情况
for (int i = l; i <= r; i++) {
// 左子数组遍历完,右子数组未遍历完
if (leftHead > m && rightHead <= r) {
array[i] = rightArray[rightHead - m - 1];
rightHead++;
// 右子数组遍历完,左子数组未遍历完
} else if (rightHead > r && leftHead <= m) {
array[i] = leftArray[leftHead - l];
leftHead++;
// 左子数组的头元素小于右子数组的头元素
} else if (leftArray[leftHead - l] < rightArray[rightHead - m - 1]) {
array[i] = leftArray[leftHead - l];
leftHead++;
// 右子数组的头元素小于左子数组的头元素
} else if (rightArray[rightHead - m - 1] <= leftArray[leftHead - l]) {
array[i] = rightArray[rightHead - m - 1];
rightHead++;
}
}
}