归并排序（Merge Sort）
归并排序（Merge Sort）
= 3 归并过程的复杂度为O(n)
归并过程 Merge
使用递归实现自顶向下的归并排序
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1int i = l, j = mid + 1;for (int k = l; k <= r; k++) {if (i > mid) { // 如果左半部分元素已经全部处理完毕arr[k] = aux[j - l];j++;} else if (j > r) { // 如果右半部分元素已经全部处理完毕arr[k] = aux[i - l];i++;} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素arr[k] = aux[i - l];i++;} else { // 左半部分所指元素 >= 右半部分所指元素arr[k] = aux[j - l];j++;}}
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void mergeSort(Comparable[] arr, int l, int r) {if (l >= r) {return;}//int mid = l + (r - l) / 2;int mid = (l + r) / 2;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);
}
public static void mergeSort(Comparable[] arr) {int n = arr.length;mergeSort(arr, 0, n - 1);
}优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
优化2: 对于小规模数组, 使用插入排序
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1int i = l, j = mid + 1;for (int k = l; k <= r; k++) {if (i > mid) { // 如果左半部分元素已经全部处理完毕arr[k] = aux[j - l];j++;} else if (j > r) { // 如果右半部分元素已经全部处理完毕arr[k] = aux[i - l];i++;} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素arr[k] = aux[i - l];i++;} else { // 左半部分所指元素 >= 右半部分所指元素arr[k] = aux[j - l];j++;}}
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void mergeSort(Comparable[] arr, int l, int r) {// 优化2: 对于小规模数组, 使用插入排序if (r - l <= 15) {InsertionSort.insertionSort(arr, l, r);return;}//int mid = l + (r - l) / 2;int mid = (l + r) / 2;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);// 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失（if判断也是需要时间的）if (arr[mid].compareTo(arr[mid + 1]) > 0) {merge(arr, l, mid, r);}
}
public static void mergeSort(Comparable[] arr) {int n = arr.length;mergeSort(arr, 0, n - 1);
}public class InsertionSort {// 对整个arr数组使用InsertionSort排序public static void insertionSort(Comparable[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {Comparable e = arr[i];int j = i;for (; j > 0 && arr[j - 1].compareTo(e) > 0; j--) {arr[j] = arr[j - 1];}arr[j] = e;}}// 对arr[l...r]的区间使用InsertionSort排序public static void insertionSort(Comparable[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {Comparable e = arr[i];int j = i;for (; j > l && arr[j - 1].compareTo(e) > 0; j--) {arr[j] = arr[j - 1];}arr[j] = e;}}
}//public static int[] copyOfRange(int[] original, int from, int to)
//int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
复制arr[3...5]
//int[] copArr = Arrays.copyOfRange(arr, 3, 5 + 1);
[7, 6, 5]
//System.out.println(Arrays.toString(copArr));
3
//System.out.println(copArr.length); Merge Sort是一个O(nlogn)复杂度的算法可以在1秒之内轻松处理100万数量级的数据注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异
//Integer[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//mergeSort(arr);
//for (int i = 0; i < arr.length; i++) {
// System.out.print(arr[i]);
// System.out.print(' ');
//}
//System.out.println();自底向上的归并排序
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1int i = l, j = mid + 1;for (int k = l; k <= r; k++) {if (i > mid) { // 如果左半部分元素已经全部处理完毕arr[k] = aux[j - l];j++;} else if (j > r) { // 如果右半部分元素已经全部处理完毕arr[k] = aux[i - l];i++;} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素arr[k] = aux[i - l];i++;} else { // 左半部分所指元素 >= 右半部分所指元素arr[k] = aux[j - l];j++;}}
}
public static void mergeSort(Comparable[] arr) {int n = arr.length;// Merge Sort Bottom Up 无优化版本for (int sz = 1; sz < n; sz *= 2) {for (int i = 0; i < n - sz; i += sz + sz) { //i+sz < n// 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));}}
}// arr {8, 6, 2, 3, 1, 5, 7, 4}
//具体分段情况
//System.out.println("l:"+i + "\t" + "mid:"+(i + sz - 1)+"\t"+"r:"+Math.min(i + sz + sz - 1, n - 1));
//l:0 mid:0 r:1
//l:2 mid:2 r:3
//l:4 mid:4 r:5
//l:6 mid:6 r:7
//
//l:0 mid:1 r:3
//l:4 mid:5 r:7
//
//l:0 mid:3 r:7优化
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1int i = l, j = mid + 1;for (int k = l; k <= r; k++) {if (i > mid) { // 如果左半部分元素已经全部处理完毕arr[k] = aux[j - l];j++;} else if (j > r) { // 如果右半部分元素已经全部处理完毕arr[k] = aux[i - l];i++;} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素arr[k] = aux[i - l];i++;} else { // 左半部分所指元素 >= 右半部分所指元素arr[k] = aux[j - l];j++;}}
}
public static void mergeSort(Comparable[] arr) {int n = arr.length;// Merge Sort Bottom Up 优化// 对于小数组, 使用插入排序优化for (int i = 0; i < n; i += 16) {InsertionSort.insertionSort(arr, i, Math.min(i + 15, n - 1));}for (int sz = 16; sz < n; sz += sz) {for (int i = 0; i < n - sz; i += sz + sz) {// 对于arr[mid] <= arr[mid+1]的情况,不进行mergeif (arr[i + sz - 1].compareTo(arr[i + sz]) > 0) {merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));}}}
}public class InsertionSort {// 对arr[l...r]的区间使用InsertionSort排序public static void insertionSort(Comparable[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {Comparable e = arr[i];int j = i;for (; j > l && arr[j - 1].compareTo(e) > 0; j--) {arr[j] = arr[j - 1];}arr[j] = e;}}
}// Merge Sort BU 也是一个O(nlogn)复杂度的算法，虽然只使用两重for循环
// 所以，Merge Sort BU也可以在1秒之内轻松处理100万数量级的数据
// 注意：不要轻易根据循环层数来判断算法的复杂度，Merge Sort BU就是一个反例练习：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。https://leetcode-cn.com/problems/sort-list/
提示：自底向上的归并排序没有使用到数组的一个重要的特性-通过索引直接获取元素
23. 合并K个排序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode/