1、项目场景：
记录一次归并排序遇坑史<br/>
一天天的，啥事也没干，尽遇坑去了
2、问题描述：
[]希尔排序在最开始给方法传递左右索引的时候，左边传递的是0，右边传递的是length-1
[]左右索引在比较的时候，没加索引和边界值重合的情况
[]定义数组的时候，考虑索引和长度，数组的长度 = 最大索引 + 1
[]遍历数组的时候，长度不要-1，长度不要-1，长度不要-1！
3、原因分析：
[]将数组分割成两份的时候，中间值是在左边的数组中的，所以右边开始的索引，应该是mid(中间值的索引)+1
[]因为在最开始传值的时候，右边的索引就是length-1，所以是可以直接等于边界值的，不加=，就会导致明明排序好了的元素，复制到原数组的时候，无法覆盖完，会存在最后一位不覆盖的情况
[]定义一个temp临时数组的空间大小的时候，right-left之后，还要+1，一位right-left是索引的大小，但是直接定义new int[]的时候，里面填入的是长度，所以要填入new int[right - left + 1]
[]数组遍历的时候，不要i < arr.length - 1
4、解决方案：
1、左边的取值是【left，mid】，右边的取值范围是【mid+1，right】
public static void sortArray(int[] initial, int left, int right) {
if(left < right){
int mid = (left + right) / 2;
//使用了递归：
// mid+1是因为，length-1，代表中间值在左边的数组中，
// 例如：数组长度为8，则right=7，mid=7/2 =3
//0-3是左边的数组，右边的自然是mid+1 = 3+1 =4
sortArray(initial, left, mid);
sortArray(initial, mid + 1, right);
mergetSort(initial, left, right, mid);
}else {
return;
}
}
2、在每个比较的地方，加上 = 号
//这里可以取到边界值，因为在传值的时候，传的就是length-1，数组不会越界
while (leftIndex <= mid && rightIndex <= right) {
if (initial[leftIndex] < initial[rightIndex]) {
//左边的小，就把左边的数放到新的数组中，以此类推直到左边或者右边的索引，到达中间的位置
temp[t++] = initial[leftIndex++];
} else {
temp[t++] = initial[rightIndex++];
}
}
//左边的索引依然没到达中间索引的位置，说明右边的索引已经达到了边界
//此时把左边所以的数，都依次放到temp数组中即可
while (leftIndex <= mid) {
temp[t++] = initial[leftIndex++];
}
while (rightIndex <= right){
temp[t++] = initial[rightIndex++];
}
- 定义temp的空间大小的时候，要【right-left+1】
//这里要+1，是因为这里是定义temp的长度，right-left只是最大的索引，长度要+1
int[] temp = new int[right - left + 1];
- 去掉length后面的 -1
for (int i = 0; i < temp.length; i++) {
initial[i+left] = temp[i];
}
5、完整的代码：
package com.yishuai.sort;
import java.util.Arrays;
/**
* @AuThor yishuai
* @description 归并排序
* @date 2021/3/23 11:12
*/
public class Merget {
public static void main(String[] args) {
int[] initial = {5, 9, 2, 8, 6, 3, 1, 4, 7};
sortArray(initial,0,initial.length - 1);
System.out.println(Arrays.toString(initial));
}
/**
* @description 分割数组
*/
public static void sortArray(int[] initial, int left, int right) {
if(left < right){
int mid = (left + right) / 2;
//使用了递归：
// mid+1是因为，length-1，代表中间值在左边的数组中，
// 例如：数组长度为8，则right=7，mid=7/2 =3
//0-3是左边的数组，右边的自然是mid+1 = 3+1 =4
sortArray(initial, left, mid);
sortArray(initial, mid + 1, right);
mergetSort(initial, left, right, mid);
}else {
return;
}
}
/**
* @Param left 数组最左边的索引
* @param right 数组最右边的索引
* @param mid 中间的索引
* @description 归并数组
*/
public static void mergetSort(int[] initial, int left, int right, int mid) {
//这里要+1，是因为这里是定义temp的长度，right-left只是最大的索引，长度要+1
int[] temp = new int[right - left + 1];
//t作为temp数组的索引
int t = 0;
//左右两个索引，都是从数组的最左边开始遍历
int leftIndex = left;
//mid+1是因为，length-1，代表中间值在左边的数组中，
// 例如：数组长度为8，则right=7，mid=7/2 =3
//0-3是左边的数组，右边的自然是mid+1 = 3+1 =4
int rightIndex = mid + 1;
//这里可以取到边界值，因为在传值的时候，传的就是length-1，数组不会越界
while (leftIndex <= mid && rightIndex <= right) {
if (initial[leftIndex] < initial[rightIndex]) {
//左边的小，就把左边的数放到新的数组中，以此类推直到左边或者右边的索引，到达中间的位置
temp[t++] = initial[leftIndex++];
} else {
temp[t++] = initial[rightIndex++];
}
}
//左边的索引依然没到达中间索引的位置，说明右边的索引已经达到了边界
//此时把左边所以的数，都依次放到temp数组中即可
while (leftIndex <= mid) {
temp[t++] = initial[leftIndex++];
}
while (rightIndex <= right){
temp[t++] = initial[rightIndex++];
}
//此时temp就是排序好之后的数组
System.out.println(Arrays.toString(temp));
for (int i = 0; i < temp.length; i++) {
initial[i+left] = temp[i];
}
}
}
发表于 2021-3-23 16:58
