1、归并排序
归并排序：O(N * logN)
public class MergeSort {
private MergeSort() {
}
/**
* 归并排序
*/
public static <E extends Comparable<E>> void sort(E[] arr) {
sort(arr, 0, arr.length - 1);
}
/**
* 归并排序 arr[l, r]
*/
private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
sort(arr, l, mid); // arr[l, mid]
sort(arr, mid + 1, r); // arr[mid + 1, r]
merge(arr, l, mid, r);
}
/**
* 合并两个有序数组 arr[l, mid] 和 arr[mid + 1, r], 使得 arr[l, r] 整体有序
*/
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
E[] temp = Arrays.copyOfRange(arr, l, r + 1);
int p1 = 0; // temp[0, mid - l]
int p2 = mid + 1 - l; // temp[mid + 1 - l, r - l]
int i = l; // arr[l, r]
while (p1 <= mid - l && p2 <= r - l) arr[i++] = temp[p1].compareTo(temp[p2]) <= 0 ? temp[p1++] : temp[p2++];
while (p1 <= mid - l) arr[i++] = temp[p1++];
while (p2 <= r - l) arr[i++] = temp[p2++];
}
}
2、归并排序优化
归并排序：O(N * logN)
优化 1：merge 条件, 对完全有序的数组 O(n)
优化 2：数据量小的时候(<=16)采用插入排序
优化 3：避免频繁的在内存中开辟空间
public class MergeSortPlus {
private MergeSortPlus() {
}
/**
* 归并排序
*/
public static <E extends Comparable<E>> void sort(E[] arr) {
E[] temp = (E[]) new Comparable[arr.length]; // 优化 3: 避免频繁的在内存中开辟空间
sort(arr, 0, arr.length - 1, temp);
}
/**
* 归并排序 arr[l, r]
*/
private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, E[] temp) {
if (r - l <= 15) {
InsertionSort.sort(arr, l, r); // 优化 2: 数据量小的时候(<=16)采用插入排序
return;
}
int mid = l + (r - l) / 2;
sort(arr, l, mid, temp); // arr[l, mid]
sort(arr, mid + 1, r, temp); // arr[mid + 1, r]
if (arr[mid].compareTo(arr[mid + 1]) > 0) merge(arr, l, mid, r, temp); // 优化 1: merge 条件
}
/**
* 合并两个有序数组 arr[l, mid] 和 arr[mid + 1, r], 使得 arr[l, r] 整体有序
*/
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
System.arraycopy(arr, l, temp, l, r - l + 1);
int p1 = l; // temp[l, mid]
int p2 = mid + 1; // temp[mid + 1, r]
int i = l; // arr[l, r]
while (p1 <= mid && p2 <= r) arr[i++] = temp[p1].compareTo(temp[p2]) <= 0 ? temp[p1++] : temp[p2++];
while (p1 <= mid) arr[i++] = temp[p1++];
while (p2 <= r) arr[i++] = temp[p2++];
}
}
3、自底向上归并排序
我们上面实现的归并排序，采用递归的写法，自顶向下进行归并排序
在这里我们换个方式，采用非递归的写法，自底向上实现归并排序
public class MergeSortBU {
private MergeSortBU() {
}
/**
* 自底向上归并排序
*/
public static <E extends Comparable<E>> void sort(E[] arr) {
int n = arr.length;
E[] temp = (E[]) new Comparable[n];
// 对 arr[0, n - 1] 中所有的 arr[i, i + 15], 使用插入排序法
for (int i = 0; i < n; i += 16) {
InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));
}
// 遍历合并的区间长度(把 2 个区间合并成 1 个区间)
for (int size = 16; size < n; size += size) {
// 合并 arr[i, i + size - 1] 和 arr[i + size, i + size + size - 1]
for (int i = 0; i + size < n; i += 2 * size) {
if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
merge(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1), temp);
}
}
}
}
/**
* 合并两个有序数组 arr[l, mid] 和 arr[mid + 1, r], 使得 arr[l, r] 整体有序
*/
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
System.arraycopy(arr, l, temp, l, r - l + 1);
int p1 = l; // temp[l, mid]
int p2 = mid + 1; // temp[mid + 1, r]
int i = l; // arr[l, r]
while (p1 <= mid && p2 <= r) arr[i++] = temp[p1].compareTo(temp[p2]) <= 0 ? temp[p1++] : temp[p2++];
while (p1 <= mid) arr[i++] = temp[p1++];
while (p2 <= r) arr[i++] = temp[p2++];
}
}