本文是 Java排序算法面试手写精讲 的分章阅读版。
分治+合并:将数组递归拆分为单个元素,然后两两合并有序子数组。
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= right) tmp[k++] = arr[j++];
System.arraycopy(tmp, 0, arr, left, tmp.length);
}
public class MergeSort {
// 优化1:提前分配临时数组,避免每次merge都new
// 优化2:小数组切换插入排序
// 优化3:如果两个子数组已经有序则跳过merge
private static final int INSERTION_THRESHOLD = 16;
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int[] tmp = new int[arr.length]; // 只分配一次
sort(arr, tmp, 0, arr.length - 1);
}
private static void sort(int[] arr, int[] tmp, int lo, int hi) {
if (lo >= hi) return;
// 优化2:小数组用插入排序
if (hi - lo + 1 < INSERTION_THRESHOLD) {
insertSort(arr, lo, hi);
return;
}
int mid = (lo + hi) >>> 1; // 无符号右移,防止溢出
sort(arr, tmp, lo, mid);
sort(arr, tmp, mid + 1, hi);
// 优化3:已有序则跳过merge
if (arr[mid] <= arr[mid + 1]) return;
merge(arr, tmp, lo, mid, hi);
}
private static void merge(int[] arr, int[] tmp, int lo, int mid, int hi) {
// 拷贝到临时数组
System.arraycopy(arr, lo, tmp, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
// 左半已耗尽
arr[k] = tmp[j++];
} else if (j > hi) {
// 右半已耗尽
arr[k] = tmp[i++];
} else if (tmp[i] <= tmp[j]) {
// 稳定性关键:相等时取左边
arr[k] = tmp[i++];
} else {
arr[k] = tmp[j++];
}
}
}
private static void insertSort(int[] arr, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
int key = arr[i];
int j = i - 1;
while (j >= lo && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
三个优化的意义:
特点: 稳定排序、时间复杂度恒定O(nlogn)、但需要O(n)额外空间。适合大数据量外部排序(归并段写磁盘)。