归并排序思想
1. 两个有序数组(arr1,arr2),在O(Math.max(arr1.length, arr2.length))时间复杂度范围可将arr1,与arr2归并为整体有序数组;空间复杂度为O(arr1.length + arr2.length);
2. 将原数组先分割为N个最小归并单元 即arr1, arr2中各一个元素,此时arr1, arr2 是有序数组,满足第1条,可进行归并;归并结果为arr3为有序数组,且arr3.length = arr1.length + arr2.length;
3. 重复log(n)次第2步,整个数组有序
有序数组归并函数
// l:左边界下标
// r: 有边界下标
// mid : 左边界最后一个元素下标
public void merge(int[] arr, int l, int mid, int r) {
int i = l;
int j = mid + 1;
// 申请临时空间
int[] temp = new int[r - l + 1];
int k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= r) {
temp[k++] = arr[j++];
}
k = 0;
for (int t = l; t <= r; t++) {
arr[t] = temp[k++];
}
}
递归实现
public void recursionMergeSort(int[] arr, int L, int R) {
if (L < R) {
// R > mid >= L
int mid = L + ((R - l) >> 1);
recursionMergeSort(arr, L, mid);
recursionMergeSort(arr, mid + 1, R);
// 第一次走到该处时一定有: R - L = 1
merge(arr, L, mid, R);
}
}
循环实现
第一次循环:将数组划分为N份最小归并单元后在归并,后续的循环会利用到之前归并有序的结果
public void stackMergeSort(int[] arr, int r) {
int k = 1;
while (k < r) {
k = k << 1;
for (int left = 0; left < r; left += k) {
int right = left + k - 1;
int mid = left + ((right - left) >> 1);
if (mid < r) {
// 右边界过界处理
right = Math.min(r, right);
merge(arr, left, mid, right);
} else {
// 右边没有元素无需合并
}
}
}
}