文章目錄
- 1. 歸并排序
- 1.1 歸并
- 1.2 遞歸
- 1.3 疊代
- 2. 數組單調和
- 3. 逆序對
1. 歸并排序
歸并排序是建立在歸并操作的基礎上的，效率為O(nlogn)。
歸并排序的實作分為遞歸實作與非遞歸(疊代)實作。
1.1 歸并
歸并(Merge)操作是指将兩個已經排序好的序列，合并成一個有序序列。
這個合并是相對比較簡單的，因為兩個序列是事先已經排序好的了，每個序列中的元素放到新序列中的順序不會改變，隻是兩個序列的元素可能會交替出現。
比如我們要歸并序列A[2, 3, 5, 6]和序列B[1, 4, 8, 9]，按照我們平時的邏輯，我們會從最左邊開始，找一個最小的，然後依次進行下去。比如這個例子，我們最小會找出1，為什麼，因為我們知道，最小的數一定在最左邊，于是看2和1，發現1比較小，是以把它挑出來放到第一個。然後我們會把2挑出來，因為現在1挑出來之後，最左邊的數的2和4，顯然2比較小，于是我們挑出2。接下來同理，3和4比較，挑出3；4和5比較，挑出4；5和8比較，挑出5；6和8比較，挑出6；最後左邊的四個數都被我們挑出來了，而右邊還剩下8和9，這時候已經沒必要挑了，剩下的數直接往後面扔就行了，因為8比6（A中的最後一個數）大，自然也比A的其他所有數都大，而B本來自身也是排好序的，是以後面的數一定比前面的大。是以我們就得出了序列[1, 2, 3, 4, 5, 6, 8, 9]。
按照上面的思路，把它反映到代碼上面，其實也是不難的。
- 首先，因為挑出來的數需要找個地方放，是以需要新開一個空間用來放這些數（合并序列）；
- 然後比較的過程就是用兩個下标分别指向兩個序列的起始位置，然後比較兩個下标所在元素的大小，挑出較小的元素放到合并序列，相應的下标往右邊移動，重複該操作直到其中一個序列結束為止；
- 最後把另一個數組的剩餘數直接拿出來放到合并序列即可。
代碼如下：
/*
* 合并兩個已排序的序列arr[start...mid]和arr[mid + 1...end]
*/
public static void merge(int[] arr, int start, int mid, int end) {
// 1. 申請輔助空間
int temp[] = new int[end - start + 1];
// 2. 從左到右進行比較
int i = start; // 指向第一個序列的開始
int j = mid + 1; // 指向第二個序列的開始
int index = 0; // 輔助空間的下标
while(i <= mid && j <= end) { // 循環直至其中一個序列結束
// 挑出較小的數
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
// 3. 将剩下的數放到合并序列的末尾
while(i <= mid) {
temp[index++] = arr[i++];
}
while(j <= end) {
temp[index++] = arr[j++];
}
// 将輔助空間的值複制到原數組
for(int k = 0; k < temp.length; k++) {
arr[start++] = temp[k];
}
} 複制
1.2 遞歸
歸并排序的一種實作方式是使用遞歸實作。這是分治政策的典型應用。
先把一個大問題分為小問題，小問題又與原先的大問題有相同的結構，可以繼續分解為小問題，直到分解為可以迅速解決的足夠小的問題，然後小問題的解決就可以反過來解決較大的問題，最終最大的那個問題（原問題）得以解決。
在這一具體的例子中，大問題就是如何把一個序列排序。要如何把這個問題分解為小問題呢？從上面提到的歸并操作入手。把這個序列分為兩半，如果這兩個序列是排序好的就好了，這樣就可以使用歸并操作對他們進行合并了。但可惜這兩個序列并不是排好序的，诶？這不就是子問題嗎？兩個較小的序列也要排序，與原問題類似，隻不過數變少了。然後子問題再用同樣的思路解決，就是分成兩半，使用歸并。一直分下去，沒完沒了了？并不會，最終會分到一個子序列隻有一個數，可以看成已經是排好序的了，不能也不需要再分。這樣一來，最小的子問題可以得到解決，那麼大問題自然就可以解決了。
代碼實作如下：
/*
* 使用遞歸的方法對序列arr[start...end]進行歸并排序
*/
public static void mergeSortRecursion(int[] arr, int start, int end) {
if (start == end) { // 待排序的序列隻有一個數，則不需要排序，開始回溯
return;
}
// 分解為兩個較小的子問題，将序列分為兩個序列，對兩個子序列進行排序
int mid = (start + end) / 2;
mergeSortRecursion(arr, start, mid);
mergeSortRecursion(arr, mid + 1, end);
// 兩個子問題解決後，再對已排序的兩個子序列進行歸并操作
merge(arr, start, mid, end);
} 複制
1.3 疊代
疊代的方法跟遞歸的思路其實是差不多的，都是使用兩兩歸并的方式進行排序，隻不過疊代不像遞歸一樣從大問題出發，而是自底向上解決問題，也就是先把最短的序列歸并，然後歸并的序列長度再依次翻倍，最終完成排序。代碼如下：
/*
* 使用疊代的方法對序列arr[start...end]進行歸并排序
*/
public static void mergeSortIteration(int[] arr, int len) {
int start, mid, end;
for(int i = 1; i < len; i *= 2) {
start = 0;
// 兩兩歸并，直到後一個子數組不存在
while(start + i < len) {
mid = start + i - 1;
end = mid + i < len ? mid + i : len - 1;
merge(arr, start, mid, end);
start = end + 1; // 歸并下一對數組
}
}
} 複制
2. 數組單調和
數組單調和，也叫數組小和，定義如下：
數組小和的定義如下：例如，數組s=[1,3,5,2,4,6]
在s[0]的左邊小于或等于s[0]的數的和為0
在s[1]的左邊小于或等于s[1]的數的和為1
在s[2]的左邊小于或等于s[2]的數的和為1+3=4
在s[3]的左邊小于或等于s[3]的數的和為1
在s[4]的左邊小于或等于s[4]的數的和為1+3+2=6
在s[5]的左邊小于或等于s[5]的數的和為1+3+5+2+4=15
是以s的小和為0+1+4+1+6+15=27
給定一個數組s，實作函數傳回s的小和。
參考文章：數組小和（單調和）
數組單調和的定義具體見這裡。
要解決這個問題，容易想到的就是二重循環暴力破解，但是這明顯是沒有辦法的辦法。其實這可以利用上面的歸并排序的方法進行求解。
首先應該明确兩個規律：
（1）對于一個序列裡面的子序列，若該子序列的單調和已經求出，那麼其内部的順序不會影響整個序列的單調和。這是顯而易見的，因為子序列内部順序的改變，并不會影響其中的元素與整個序列其他元素的前後大小關系，是以不會影響單調和。
（2）在歸并的過程中，如果遇到左邊序列的一個數A比右邊序列的某個數B小，那麼A也一定小于B的右邊的所有數。這是由待歸并的子序列已經排好序的性質決定的。
根據以上兩條規律，可以對歸并排序的代碼做如下調整，使其可以用來求數組單調和：
public static int getSmallSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return mergeSortRecursion(arr, 0, arr.length - 1);
}
/*
* 合并兩個已排序的序列arr[start...mid]和arr[mid + 1...end]
*/
public static int merge(int[] arr, int start, int mid, int end) {
int smallSum = 0; // 用以累計數組小和
int temp[] = new int[end - start + 1]; // 申請輔助空間
int index = 0; // 輔助空間的下标
int i = start; // 指向第一個序列的開始
int j = mid + 1; // 指向第二個序列的開始
while(i <= mid && j <= end) { // 循環直至其中一個序列結束
if (arr[i] <= arr[j]) { // 挑出較小的數
smallSum += arr[i] * (end - j + 1); // 根據第二條規律
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
// 将剩下的數放到合并序列的末尾
while(i <= mid) {
temp[index++] = arr[i++];
}
while(j <= end) {
temp[index++] = arr[j++];
}
// 将輔助空間的值複制到原數組
for(int k = 0; k < temp.length; k++) {
arr[start++] = temp[k];
}
return smallSum;
}
/*
* 使用遞歸的方法對序列arr[start...end]進行歸并排序
*/
public static int mergeSortRecursion(int[] arr, int start, int end) {
if (start == end) { // 待排序的序列隻有一個數，則不需要排序，開始回溯
return 0;
}
// 分解為兩個較小的子問題，将序列分為兩個序列，對兩個子序列進行排序
int mid = (start + end) / 2;
int left = mergeSortRecursion(arr, start, mid);
int right = mergeSortRecursion(arr, mid + 1, end);
// 兩個子問題解決後，再對已排序的兩個子序列進行歸并操作
int whole = merge(arr, start, mid, end);
return left + right + whole;
} 複制
3. 逆序對
在一個序列中，若前面的一個數大于後面一個數字，則這兩個數字組成一個逆序對。
問題：給定一個數組，求出其逆序對個數。
這個問題也可以使用上面類似的方法求解，隻不過是在左邊的數大于右邊時逆序對的數量累加。歸并操作代碼如下：
/*
* 合并兩個已排序的序列arr[start...mid]和arr[mid + 1...end]
*/
public static int merge(int[] arr, int start, int mid, int end) {
int inverseNum = 0; // 用以累計數組小和
int temp[] = new int[end - start + 1]; // 申請輔助空間
int index = 0; // 輔助空間的下标
int i = start; // 指向第一個序列的開始
int j = mid + 1; // 指向第二個序列的開始
while(i <= mid && j <= end) { // 循環直至其中一個序列結束
if (arr[i] <= arr[j]) { // 挑出較小的數
temp[index++] = arr[i++];
} else {
inverseNum += mid - i + 1;
temp[index++] = arr[j++];
}
}
// 将剩下的數放到合并序列的末尾
while(i <= mid) {
temp[index++] = arr[i++];
}
while(j <= end) {
temp[index++] = arr[j++];
}
// 将輔助空間的值複制到原數組
for(int k = 0; k < temp.length; k++) {
arr[start++] = temp[k];
}
return inverseNum;
} 複制
逆序對可以用來判斷一個八數位問題是否有解，思想是：一個八數位，對其進行進行移位操作，不會改變其逆序對總數的奇偶性。是以通過求初始八數位和目标八數位的逆序對，判斷其奇偶性是否相同，就可判斷是否可以到達目标狀态，即是否有解。