核心思想
归并排序实质是利用分治思想,先拆分,再合并。
拆分:将待排序数组从中间切分,并对切分后的子数组做同样的切分操作,直到子数组中只有一个元素为止,只有一个元素的数组一定是有序的。也就是说切分之后做到了局部有序。
合并:对两个局部有序的数组进行合并操作,使合并结果也是有序的。
合并过程涉及到三个循环不变量:
k:表示原数组中将要赋值的位置,边界为闭区间:所有参与比较的元素的最左边索引到最右边索引。
i:表示第一个数中要参与比较的元素的位置,边界为第一个数组的第一个元素到第一个数组的最后一个元素,如果i超出边界,对第二个数组中的元素进行一一复制即可。
j:表示第二个数组中要参与比较的元素的位置,边界为第二个数组的第一个元素到第二个数组的最后一个元素,如果j超出边界,对第一个数组中的元素一一赋值即可。
理解归并排序前,建议先理解合并两个有序数组的操作。
代码实现
package com.zw6688.al.sort;
import java.util.Arrays;
/**
* @Author:
* @Description: 归并排序
* @Date: 2021/4/21 20:21
*/
public class MergeSort {
public static void main(String[] args) {
int[] nums = {6, 5, 2, 3, 8, 7, 9, 1};
MergeSort mergeSort = new MergeSort();
mergeSort.split(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
public void split(int[] nums, int left, int right) {
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
split(nums, left, mid);
split(nums, mid + 1, right);
merge(nums, left, mid, right);
}
public void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
for (int i = 0; i < right - left + 1; i++) {
temp[i] = nums[left + i];
}
// int k = left; //表示要赋值的位置
int i = 0; //左半部分的将要比较的元素
int j = mid - left + 1; //右半部分将要比较的元素
for (int k = left; k <= right; k++) {
if (i >= mid -left + 1) {
nums[k] = temp[j];
j++;
} else if (j >= right - left + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] > temp[j]) {
nums[k] = temp[j];
j++;
} else {
nums[k] = temp[i];
i++;
}
}
}
}