arr先保证局部有序,再慢慢变得整体有序
实际并没有分割数组
public static void mergeSort(int[] arr, int left, int right, int mid) {
// 归并排序的过程是先分组,然后两两合并,最终变得有序
// 左指针不小于右指针时,递归结束
if (left >= right) {
return;
}
// 先分组左半部分,本质是将指针指向
mergeSort(arr, left, mid, (left + mid) / 2);
// 再分组右半部分
mergeSort(arr, mid + 1, right, (mid + 1 + right) / 2);
// 分好组之后,合并排序
sort(arr, left, right, mid);
}
public static void sort(int[] arr, int left, int right, int mid) {
// 临时数组保存排序数据
int[] temp = new int[right - left + 1];
int s1 = left;
int s2 = mid + 1;
// 比较两个序列之间的最小数谁最小,放入temp中
int i = 0;
while (s1 <= mid && s2 <= right) {
if (arr[s1] < arr[s2]) {
temp[i] = arr[s1];
i++;
s1++;
} else {
temp[i] = arr[s2];
i++;
s2++;
}
}
// 将剩余数字放入temp中
while (s1 <= mid) {
temp[i] = arr[s1];
i++;
s1++;
}
while (s2 <= right) {
temp[i] = arr[s2];
i++;
s2++;
}
// 数据从临时数组取出,覆盖原数组
for (int j = 0; j < temp.length; j++) {
// 注意是left + j,因为temp是小数组
arr[left + j] = temp[j];
}
}