與歸併排序相關的一些問題
與歸併排序相關的一些問題
作者：Grey
原文地址：
歸併排序的遞歸解法
插入，選擇，冒泡排序時間複雜度是O(N^2)，歸併排序可以做到時間複雜度O(N*logN)。
歸併排序的整體思路是利用遞歸，先讓左邊排好序，再讓右邊排好序，然後通過merge操作讓整體有序。
merge操作類似合併兩個及以上有序鏈表問題中提到的算法。
但是merge過程需要輔助數組，所以額外空間複雜度為O(N)。
完整代碼和注釋見：
public class Code_MergeSort {
// 遞歸方法實現
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
// 遞歸過程，讓l...r變有序
public static void process(int[] arr, int l, int r) {
if (l == r) {
return;
}
// 求中點
int mid = l + ((r - l) >> 1);
// 左邊部分有序
process(arr, l, mid);
// 右邊部分有序
process(arr, mid + 1, r);
// 整體變有序
merge(arr, l, mid, r);
}
// arr[l...mid]已經有序
// arr[mid+1...r]也已經有序
// 將arr[l...r]整體變有序
public static void merge(int[] arr, int l, int mid, int r) {
// 輔助數組
int[] help = new int[r - l + 1];
int ls = l;
int rs = mid + 1;
int i = 0;
while (ls <= mid && rs <= r) {
// 誰小拷貝誰到輔助數組中。
if (arr[ls] < arr[rs]) {
help[i++] = arr[ls++];
} else {
help[i++] = arr[rs++];
}
}
// 左邊和右邊剩餘部分直接拷貝到輔助數組中
while (ls <= mid) {
help[i++] = arr[ls++];
}
while (rs <= r) {
help[i++] = arr[rs++];
}
i = 0;
for (int n : help) {
arr[l + (i++)] = n;
}
}
}
這個遞歸過程時間複雜度可以利用 master 公式來計算。
T(N) = 2*T(N/2) + O(N^1)
故上述算法時間複雜度為O(N*logN)
歸併排序的迭代版本實現
因為任何遞歸函數都可以用非遞歸函數來實現，所以，歸併排序有對應的迭代方法，思路如下
-
設置一個步長，從 1 開始，1，2，4，8，16….2^n 方式遞增
-
每次處理對應步長的數組區間範圍內的排序。
-
步長超過或者等於數組長度，則整個數組排序完成。
比如[1,3,4,2,5,6,4,6,8]
先設置步長為 1，數組分成如下區間
[0...1],[2...3],[4...5],[6...7],[8...8]
註：最後一組不夠分，則單獨作為一組處理。
將如上區間內部排好序，得到的數組為
[1,3,2,4,5,6,4,6,8]
然後設置步長為 2，數組分成如下區間
[0...3],[4...7],[8...8]。
然後將上述區間內部先排好序，得到數組為
[1,2,3,4,4,5,6,6,8]
然後設置步長為 4，數組分成如下區間
[0...7],[8...8]。
然後將上述區間內部先排好序，得到數組為
[1,2,3,4,4,5,6,6,8]
最後設置步長為 8，數組只有一個區間，直接排序，得到最後結果
[1,2,3,4,4,5,6,6,8]
完整代碼見
public class Code_MergeSort {
// 歸併排序的迭代版
public static void mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int len = arr.length;
// 步長，1，2，4，8....
int step = 1;
while (step < len) {
// 左組的第一個位置
int lStart = 0;
while (lStart < len) {
if (lStart + step >= len) {
// 沒有右組
break;
}
int mid = lStart + step - 1;
// rEnd不能越界
int rEnd = mid + Math.min(step, len - mid - 1);
// 右組中第一個位置
// 中點位置
merge(arr, lStart, mid, rEnd);
lStart = rEnd + 1;
}
// 防止溢出
if (step > (len / 2)) {
break;
}
step <<= 1;
}
}
// arr[l...mid]已經有序
// arr[mid+1...r]也已經有序
// 將arr[l...r]整體變有序
public static void merge(int[] arr, int l, int mid, int r) {
// 輔助數組
int[] help = new int[r - l + 1];
int ls = l;
int rs = mid + 1;
int i = 0;
while (ls <= mid && rs <= r) {
// 誰小拷貝誰到輔助數組中。
if (arr[ls] < arr[rs]) {
help[i++] = arr[ls++];
} else {
help[i++] = arr[rs++];
}
}
// 左邊和右邊剩餘部分直接拷貝到輔助數組中
while (ls <= mid) {
help[i++] = arr[ls++];
}
while (rs <= r) {
help[i++] = arr[rs++];
}
i = 0;
for (int n : help) {
arr[l + (i++)] = n;
}
}
}
合併有序數組
題目描述見LeetCode 88. Merge Sorted Array
本題思路就是歸併排序的merge過程，不贅述，代碼如下
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len = m + n;
while (m > 0 && n > 0) {
if (nums1[m - 1] > nums2[n - 1]) {
nums1[--len] = nums1[--m];
} else {
nums1[--len] = nums2[--n];
}
}
while (n > 0) {
nums1[--len] = nums2[--n];
}
}
}
註：本題在 LintCode 中也有，見LintCode 6 · Merge Two Sorted Arrays
在 LintCode 中，對本題有個擴展要求：
如果一個數組很大，另一個數組很小，你將如何優化算法？
對於擴展要求，我們可以用如下方式來優化
即直接查小數組中的元素在大數組中的位置（可以用二分），然後依次填入具體位置
完整代碼見
public class Solution {
public static int[] mergeSortedArray(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int[] bigger = m >= n ? A : B;
int[] smaller = bigger == A ? B : A;
int[] helper = new int[m + n];
int from = 0;
int to;
int index = 0;
for (int i = 0; i < smaller.length; i++) {
int position = position(smaller[i], bigger, i);
helper[position] = smaller[i];
to = position - 1;
while (from <= to) {
helper[from++] = bigger[index++];
}
from = position + 1;
}
while (from < (m + n)) {
helper[from++] = bigger[index++];
}
return helper;
}
// value在bigger的位置是多少
public static int position(int value, int[] bigger, int offset) {
int smallerThanMe = 0;
int L = 0;
int R = bigger.length - 1;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (bigger[mid] > value) {
R = mid - 1;
} else if (bigger[mid] < value) {
smallerThanMe = (mid + 1);
L = mid + 1;
} else {
smallerThanMe = mid;
R = mid - 1;
}
}
return smallerThanMe + offset;
}
}
計算右側小於當前元素的個數問題
題目描述見：LeetCode 315. Count of Smaller Numbers After Self
本題也是利用了歸併排序的merge過程，由於歸併排序是從小到大排序，而我們需要得到某個元素右側有多少比它小，所以我們還需要將歸併排序改成從大到小排序。
以某一次merge過程為例，比如
左側區間（已排好序）: [5,3,2,1]
右側區間（已排好序）：[6,4,3,3]
示例圖如下
當左側指針來到s1的時候，右側指針移動到s2的時候，開始比左側的值要小，此時可以結算s1位置右側有幾個比它小的元素。
左側組中比 s1 更小的元素個數 + (r - s2 + 1)
完整代碼見：
class Solution {
public static class Node {
public int value;
public int index;
public Node(int index, int value) {
this.value = value;
this.index = index;
}
}
// 思路轉換為：一個數的右邊有多少個數比它小！
// 改歸併排序（從大到小）
public static List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<>(nums.length);
Node[] nodes = new Node[nums.length];
for (int i = 0; i < nums.length; i++) {
result.add(0);
nodes[i] = new Node(i, nums[i]);
}
process(nodes, 0, nums.length - 1, result);
return result;
}
private static void process(Node[] nodes, int l, int r, List<Integer> result) {
if (l == r) {
return;
}
int m = l + ((r - l) >> 1);
process(nodes, l, m, result);
process(nodes, m + 1, r, result);
merge(nodes, l, m, r, result);
}
private static void merge(Node[] nodes, int l, int m, int r, List<Integer> result) {
Node[] help = new Node[r - l + 1];
int s1 = l;
int s2 = m + 1;
int index = 0;
while (s1 <= m && s2 <= r) {
if (nodes[s1].value > nodes[s2].value) {
result.set(nodes[s1].index, result.get(nodes[s1].index) + r - s2 + 1);
help[index++] = nodes[s1++];
} else if (nodes[s1].value < nodes[s2].value) {
help[index++] = nodes[s2++];
} else {
help[index++] = nodes[s2++];
}
}
while (s1 <= m) {
help[index++] = nodes[s1++];
}
while (s2 <= r) {
help[index++] = nodes[s2++];
}
for (int i = 0; i < help.length; i++) {
nodes[l + i] = help[i];
}
}
}
LintCode上有一個類似的題目，題目描述見：LintCode 532 · Reverse Pairs
本題的思路和上一題一致，都是先將歸併排序改成從大到小排序，然後在merge過程中，求一個數右側有幾個數比它小，不贅述，代碼見：
public class Solution {
public static long reversePairs(int[] A) {
if (null == A || A.length < 2) {
return 0;
}
return process(A, 0, A.length - 1);
}
private static long process(int[] a, int l, int r) {
if (l == r) {
return 0L;
}
int m = l + ((r - l) >> 1);
return process(a, l, m) + process(a, m + 1, r) + merge(a, l, m, r);
}
private static long merge(int[] a, int l, int m, int r) {
int[] help = new int[r - l + 1];
int index = 0;
int s1 = l;
int s2 = m + 1;
long ans = 0L;
while (s1 <= m && s2 <= r) {
if (a[s1] < a[s2]) {
help[index++] = a[s2++];
} else if (a[s1] > a[s2]) {
ans += (r - s2 + 1);
help[index++] = a[s1++];
} else {
help[index++] = a[s2++];
}
}
while (s1 <= m) {
help[index++] = a[s1++];
}
while (s2 <= r) {
help[index++] = a[s2++];
}
index = 0;
for (int n : help) {
a[l + (index++)] = n;
}
return ans;
}
}
翻轉對問題
題目描述見：LeetCode 493. Reverse Pairs
本題也是利用merge過程，不同於上述兩個問題，本題在merge兩個區間之前，就要先統計一下num[i] > 2 * num[j]的數量。
完整代碼見：
class Solution {
public static int reversePairs(int[] A) {
if (null == A || A.length < 2) {
return 0;
}
int size = A.length;
return process(A, 0, size - 1);
}
public static int process(int[] a, int l, int r) {
if (l == r) {
return 0;
}
int m = l + ((r - l) >> 1);
return process(a, l, m) + process(a, m + 1, r) + merge(a, l, m, r);
}
public static int merge(int[] a, int l, int m, int r) {
// 先執行統計
int ans = 0;
int s1 = l;
int s2 = m + 1;
while (s1 <= m && s2 <= r) {
if ((long) a[s1] - (long) a[s2] > (long) a[s2]) {
ans += (r - s2 + 1);
s1++;
} else {
s2++;
}
}
// 以下是經典mergesort排序
int[] help = new int[r - l + 1];
s1 = l;
s2 = m + 1;
int index = 0;
while (s1 <= m && s2 <= r) {
if (a[s1] < a[s2]) {
help[index++] = a[s2++];
} else if (a[s1] > a[s2]) {
help[index++] = a[s1++];
} else {
help[index++] = a[s2++];
}
}
while (s1 <= m) {
help[index++] = a[s1++];
}
while (s2 <= r) {
help[index++] = a[s2++];
}
index = 0;
for (int n : help) {
a[l + (index++)] = n;
}
return ans;
}
}
區間和的個數問題
題目描述見：LeetCode 327. Count of Range Sum
本題有幾個優化點：
-
由於需要快速得到區間和，所以，可以通過前綴和數組來加速區間和的求法。
-
在
merge過程中，由於存在單調性，所以可以通過滑動窗口的方式，定位到區間和的上下界，整個過程不回退，所以不會增加歸併排序的整體時間複雜度。
完整代碼和注釋見
class Solution {
public static int countRangeSum(int[] nums, int lower, int upper) {
int size = nums.length;
// 前綴和數組加速求區間的和！！
long[] preSum = new long[size];
preSum[0] = nums[0];
for (int i = 1; i < size; i++) {
preSum[i] = nums[i] + preSum[i - 1];
}
return p(preSum, 0, size - 1, lower, upper);
}
public static int p(long[] preSum, int i, int j, int lower, int upper) {
if (i == j) {
if (preSum[i] >= lower && preSum[j] <= upper) {
return 1;
}
return 0;
}
int mid = i + ((j - i) >> 1);
return p(preSum, i, mid, lower, upper) + p(preSum, mid + 1, j, lower, upper) + merge(preSum, i, mid, j, lower, upper);
}
private static int merge(long[] preSum, int i, int mid, int j, int lower, int upper) {
// 單調性->滑動窗口
int pair = 0;
int L = i;
int R = i;
int S = mid + 1;
// 區間和存在單調性，使用滑動窗口定位上下界，不回退，所以O(logN)
while (S <= j) {
long max = preSum[S] - lower;
long min = preSum[S] - upper;
while (L <= mid && preSum[L] < min) {
L++;
}
while (R <= mid && preSum[R] <= max) {
R++;
}
pair += (R - L);
S++;
}
// mergeSort經典代碼
long[] helper = new long[j - i + 1];
int l = i;
int r = mid + 1;
int index = 0;
while (l <= mid && r <= j) {
if (preSum[l] > preSum[r]) {
helper[index++] = preSum[r++];
} else {
helper[index++] = preSum[l++];
}
}
while (l <= mid) {
helper[index++] = preSum[l++];
}
while (r <= j) {
helper[index++] = preSum[r++];
}
int k = 0;
for (long num : helper) {
preSum[i + (k++)] = num;
}
return pair;
}
}
