实验没有成功，明日再战！！！
public class MergeSort {
public static void main(String[] args) {
int [] arr = {1,4,5,8,2,9,3};
mergeSort(arr);
System.out.println(Arrays.asList(arr));
}
public static void mergeSort(int[] arr){
//1.arr == null 放在前面（可考虑）
if(arr == null || arr.length == 0){
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr,int left,int right){
if(left >= right){
return;
}
//1.取出数组的中间值（死记这个方法,向右移位可以避免数组溢出）
int middle = left + ((right - left) >> 1);
//2.开始递归操作
//2.1 对左边进行递归
mergeSort(arr, left, middle);
//2.2 对右边进行递归
mergeSort(arr, middle + 1, right);
//3.对最后的结果进行合并
merge(arr,left,middle,right);
}
public static void merge(int[] arr,int left,int middle,int right){
//1.1 初始化一个数组：用来临时存储归并后的数据
int[] temp = new int[right - left + 1];
//1.2 初始化一个指针：用来添加数字
int index = 0;
//1.3 初始化传入数组中的左右开始指针
int newLeft = left;
int newRight = middle + 1;
//2.开始向temp中插入数字(为什么是<=)
while(newLeft <= middle && newRight <= right){
if(arr[newLeft] > arr[newRight]){
temp[index++] = arr[newRight++];
}else{
temp[index++] = arr[newLeft++];
}
}
//3.要考虑左右两边都没有元素的情况
while(newLeft <= middle){
temp[index++] = arr[left++];
}
while(newRight <= right){
temp[index++] = arr[right++];
}
//4.把temp里面的值赋值给arr
for (int i = 0; i < temp.length; i++) {
//left + i对应的具体位置
arr[left+i] = temp[i];
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/202569.html
