原理说明：
- 将程序中待排序数字分为若干组，每个数字分为一组
- 将若干个组件两两合并，保证合并后的组是有序的
- 重复第二步操作直到只剩下一组，排序完成
思想示意图：
代码实现：
import java.util.Arrays;
public class MergetSort {
public static void main(String[] args) {
int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
int temp[] = new int[arr.length]; // 归并排序需要一个额外空间
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("归并排序后=" + Arrays.toString(arr));
}
// 分 + 合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; // 中间索引
// 向左递归进行分解
mergeSort(arr, left, mid, temp);
// 向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
// 合并
merge(arr, left, mid, right, temp);
}
}
// 合并的方法
/**
*
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 初始化i，左边有序序列的初始索引
int j = mid + 1; // 初始化j，右边有序序列的初始索引
int t = 0; // 指向temp数组的当前索引
//（一）
// 先把左右两边（有序）的数据按照规则填充到temp数组
// 直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) { // 继续
// 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
// 即将左边的当前元素，填充到temp数组
// 然后 t++，i++
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else { // 反之，将右边有序序列的当前元素，填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
// (二)
// 把有剩余数据的一边的数据依次全部填充到temp
while (i <= mid) { // 左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) { // 右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
// (三)
// 将temp数组的元素拷贝到arr
// 注意，并不是每次都拷贝所有
t = 0;
int tempLeft = left; //
// 第一次合并 tempLeft = 0, right = 1 // tempLeft = 2 right = 3 // tL = 0 ri = 3
// 最后一次tempLeft = 0 right = 7
System.out.println("tempLeft = " + tempLeft + " right =" + right);
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
运行结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/131146.html
