前言

我們所熟知的快速排序和歸并排序都是非常優(yōu)秀的排序算法。

但是快速排序和歸并排序的一個(gè)區(qū)別就是：快速排序是一種內(nèi)部排序，而歸并排序是一種外部排序。

簡單理解歸并排序：遞歸地拆分，回溯過程中，將排序結(jié)果進(jìn)行合并。

大致流程示意圖：

?

假設(shè)遞歸的終止條件就是剩下三個(gè)以下的元素就可以排序了。

注意：這步合并的過程用到了額外的存儲空間。完成了排序之后再復(fù)制回去。

二路歸并演示代碼

#include <iostream>
using namespace std;void merge_sort(int *arr, int l, int r) {// 遞歸終止條件：只有一個(gè)元素或者沒有元素的時(shí)候，不需要排序。if (l >= r) return ;// 打印輸出排序之前的情況cout << endl;cout << "sort " << l << "<-->" << r << " : ";for (int i = l; i <= r; i++) cout << arr[i] << " ";cout << endl;int mid = (l + r) >> 1;merge_sort(arr, l, mid); // left sortmerge_sort(arr, mid + 1, r); // right sort// 寫遞歸代碼，一定不要展開地看，上面兩行代碼就當(dāng)做左右子區(qū)間已經(jīng)排序好了。// 下面將對兩個(gè)區(qū)間進(jìn)行合并，需要開辟新的空間將元素存到temp數(shù)組中。int *temp = (int *)malloc(sizeof(int) * (r - l + 1));int k = 0, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if ((p2 > r) || (p1 <= mid && arr[p1] <= arr[p2])) {// 只有當(dāng)右邊為空，或者左邊不為空并且左邊比右邊小，才將左邊的元素放入temp[k++] = arr[p1++];} else {temp[k++] = arr[p2++];}}// 最后再拷貝回去即可for (int i = l; i <= r; i++) arr[i] = temp[i - l];// 打印輸出排序之后的情況for (int i = l; i <= r; i++) cout << arr[i] << " ";cout << endl;free(temp);return ;
}int main() {int n;int arr[100];cin >> n;for (int i = 0; i < n; i++) cin >> arr[i];merge_sort(arr, 0, n - 1);for (int i = 0; i < n; i++) cout << arr[i] << " ";return 0;
}

輸入數(shù)據(jù)：

10 
7 9 0 8 6 4 5 3 1 2

輸出：

sort 0<-->9 : 7 9 0 8 6 4 5 3 1 2 sort 0<-->4 : 7 9 0 8 6 sort 0<-->2 : 7 9 0 sort 0<-->1 : 7 9 
7 9 
0 7 9 sort 3<-->4 : 8 6
6 8
0 6 7 8 9sort 5<-->9 : 4 5 3 1 2sort 5<-->7 : 4 5 3sort 5<-->6 : 4 5
4 5
3 4 5sort 8<-->9 : 1 2
1 2
1 2 3 4 5
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

多路歸并

上述演示代碼的歸并排序只是二路歸并。將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組。

那么多路歸并就很好理解了，就是將多個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組。

比如三路歸并：

?關(guān)于多路歸并排序的應(yīng)用，有一道很經(jīng)典的面試題：

意思就是：我的內(nèi)存太小了，無法通過諸如快速排序這樣的內(nèi)部排序算法，進(jìn)行數(shù)據(jù)的直接整體排序。那么為什么這個(gè)問題可以由歸并算法來解決呢？

歸并的時(shí)候，外存可以作為歸并排序中的那片關(guān)鍵的額外空間，數(shù)據(jù)是可以直接寫回外存的，所以不需要內(nèi)存有40GB的額外空間來先存放排序完的數(shù)據(jù)，再寫回外存。

其實(shí)這40GB的文件可以被拆分成20份2GB的小文件，我們只要分別對20份小文件進(jìn)行排序之后，進(jìn)行20路歸并操作就可以了

注意：程序執(zhí)行一定是在內(nèi)存當(dāng)中，所有的數(shù)據(jù)也都需要從輔存或者外存當(dāng)中調(diào)入內(nèi)存當(dāng)中，才可以進(jìn)行CPU的運(yùn)算。一個(gè)2GB大小的內(nèi)存當(dāng)然無法調(diào)入40GB的數(shù)據(jù)。

還需注意的是：我們在程序中只存儲了相應(yīng)的文件指針，并沒有將文件中的內(nèi)容一次性全部讀滿內(nèi)存，而是需要一個(gè)數(shù)據(jù)就從文件中讀一個(gè)數(shù)據(jù)。

讀取文件演示代碼：

*************************************************************************> File Name: merge_file.cpp> Author: jby> Mail: > Created Time: Sat 12 Aug 2023 11:39:20 PM CST************************************************************************/#include<iostream>
using namespace std;int main(int argc, char *argv[]) {int n = argc - 1; // 讀取文件數(shù)量FILE **farr = (FILE **)malloc(sizeof(FILE *) * n);for (int i = 1; i <= n; i++) {farr[i - 1] = fopen(argv[i], "r");}for (int i = 0; i < n; i++) {int a;while (~fscanf(farr[i], "%d", &a)) {printf("%d\n", a);}printf("======\n");}return 0;
}

生成倆數(shù)據(jù)文件：file1、file2

# file1
1
34
56
78

# file2:
3
45
89
100

執(zhí)行命令行：$./a.out file1 file2

輸出結(jié)果：

1
34
56
78
======
3
45
89
100
======

這樣我們就依次讀取了存放在兩個(gè)文件中的數(shù)據(jù)。

文件排序演示代碼（簡單實(shí)現(xiàn)，不用歸并）

/*************************************************************************> File Name: merge_file.cpp> Author: jby> Mail: > Created Time: Sat 12 Aug 2023 11:39:20 PM CST************************************************************************/#include<iostream>
using namespace std;struct Data {FILE *fin;     // fin: 當(dāng)前文件指針int val, flag; // val: 當(dāng)前讀取的值；flag: 當(dāng)前文件是否為空
};int main(int argc, char *argv[]) {int n = argc - 1; // 讀取文件數(shù)量Data *data = (Data *)malloc(sizeof(Data) * n);for (int i = 1; i <= n; i++) {data[i - 1].fin = fopen(argv[i], "r");if (fscanf(data[i - 1].fin, "%d", &data[i - 1].val) == EOF) {data[i - 1].flag = 1;} else {data[i - 1].flag = 0;}}FILE *fout = fopen("output", "w");while (1) {int flag = 0;int ind = -1;int minVal = 0x3f3f3f3f;for (int i = 0; i < n; i++) {if (data[i].flag) continue; // 當(dāng)前文件為空if (ind == -1 || data[i].val < data[ind].val) {ind = i;}}if (ind != -1) {fprintf(fout, "%d\n", data[ind].val); // 向結(jié)果文件中輸出內(nèi)容if (fscanf(data[ind].fin, "%d", &data[ind].val) == EOF) {data[ind].flag = 1;} else {data[ind].flag = 0;}flag = 1;}if (flag == 0) break;}return 0;
}

執(zhí)行命令行：$./a.out file1 file2

輸出結(jié)果，保存在output文件中：

1
3
34
45
56
78
89
100

歸并排序的算法思想

我們不妨把思維從排序問題當(dāng)中延展出來，歸并排序的算法思想可以看成是以下三個(gè)步驟：

1. 左邊處理一下，得到左邊的信息
2. 右邊處理一下，得到右邊的信息
3. 最后再處理，橫跨左右兩邊的信息

這就是分而治之的思想。

LeetCode刷題實(shí)戰(zhàn)

劍指 Offer 51. 數(shù)組中的逆序?qū)?/h3>

在歸并排序的過程中，當(dāng)右邊區(qū)間的元素放進(jìn)額外空間的時(shí)候，左邊剩下的元素個(gè)數(shù)就是該元素所對應(yīng)的逆序?qū)€(gè)數(shù)。所以可以在歸并的過程中不斷累加。

class Solution {
public:vector<int> temp;int countResult(vector<int>& nums, int l, int r) {if (l >= r) return 0; // 如果只有一個(gè)元素，逆序數(shù)為0int ans = 0, mid = (l + r) >> 1;ans += countResult(nums, l, mid);ans += countResult(nums, mid + 1, r);int k = l, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if ((p2 > r) || (p1 <= mid && nums[p1] <= nums[p2])) {temp[k++] = nums[p1++];} else {temp[k++] = nums[p2++];ans += (mid - p1 + 1);}}for (int i = l; i <= r; i++) nums[i] = temp[i];return ans;}int reversePairs(vector<int>& nums) {while (temp.size() < nums.size()) temp.push_back(0);return countResult(nums, 0, nums.size() - 1);       }
};

23. 合并 K 個(gè)升序鏈表 - 力扣（LeetCode）

這道題其實(shí)跟之前的文件排序演示代碼的邏輯沒有本質(zhì)區(qū)別，只不過這道題可以用到堆來加速。

class Solution {
public:struct CMP {bool operator()(ListNode *p, ListNode *q) {return p->val > q->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode *, vector<ListNode *>, CMP> q;for (auto x : lists) {if (x == nullptr) continue;q.push(x);}ListNode ret, *p = &ret;while (!q.empty()) {ListNode *cur = q.top();q.pop();p->next = cur;p = cur;if (cur->next) q.push(cur->next);}return ret.next;}
};

148. 排序鏈表 - 力扣（LeetCode）


?

如何用歸并排序?qū)崿F(xiàn)鏈表的排序呢？下面這段代碼還是很具有典型意義的用鏈表來實(shí)現(xiàn)過程。

lass Solution {
public:ListNode *mergeSort(ListNode *head, int n) {if (head == nullptr || head->next == nullptr) return head;int l = n / 2, r = n - l;ListNode *lp = head, *rp = lp, *p;for (int i = 1; i < l; i++, rp = rp->next);p = rp, rp = rp->next;p->next = nullptr;lp = mergeSort(lp, l); // left Sortrp = mergeSort(rp, r); // right SortListNode ret;p = &ret;while (lp || rp) {if (rp == nullptr || (lp && lp->val < rp->val)) {p->next = lp;lp = lp->next;p = p->next;} else {p->next = rp;rp = rp->next;p = p->next;}}return ret.next;}ListNode* sortList(ListNode* head) {int n = 0;ListNode *p = head;while (p) p = p->next, n += 1;return mergeSort(head, n);}
};

1305. 兩棵二叉搜索樹中的所有元素 - 力扣（LeetCode）

用中序遍歷，歸并兩顆子樹，也是具有一定綜合性的題。（怎么說的跟考研數(shù)學(xué)似的。。。）

class Solution {
public:void getResult(TreeNode *root, vector<int> &arr) {if (root == nullptr) return ;getResult(root->left, arr);arr.push_back(root->val);getResult(root->right, arr);return ;}vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {vector<int> lnums, rnums;getResult(root1, lnums);getResult(root2, rnums);vector<int> ret;int p1 = 0, p2 = 0;while (p1 < lnums.size() || p2 < rnums.size()) {if (p2 >= rnums.size() || (p1 < lnums.size() && lnums[p1] < rnums[p2])) {ret.push_back(lnums[p1++]);} else {ret.push_back(rnums[p2++]);}}return ret;}
};

327. 區(qū)間和的個(gè)數(shù) - 力扣（LeetCode）

一說到區(qū)間和值，就能想到前綴和。區(qū)間和等于前綴和數(shù)組中兩項(xiàng)相減的值。問題就變成了，前綴和數(shù)組中，有多少對 lower <= sun[i]-sum[j] <= upper (i>j)

利用左右區(qū)間的有序性，加速查找的過程。

算法解題過程的封裝思維：當(dāng)我們將問題轉(zhuǎn)化成另一個(gè)問題的時(shí)候，我們就忘掉前面的問題到底是什么，只需專注解決當(dāng)前這個(gè)獨(dú)立的問題。而不是腦子里一團(tuán)亂麻。

class Solution {
public:int countTwoPart(vector<long long> &sum, int l1, int r1, int l2, int r2, int lower, int upper) {int ans = 0, k1 = l1, k2 = l1;for (int j = l2; j <= r2; j++) {long long a = sum[j] - upper;long long b = sum[j] - lower;while (k1 <= r1 && sum[k1] < a) k1++;while (k2 <= r1 && sum[k2] <= b)k2++;ans += k2 - k1;}return ans;}int mergeSort(vector<long long> &sum, int l, int r, int lower, int upper) {if (l >= r) return 0; // 只有一個(gè)元素的話，根本找不到數(shù)值對。int mid = (l + r) >> 1, ans = 0;ans += mergeSort(sum, l, mid, lower, upper);ans += mergeSort(sum, mid + 1, r, lower, upper);ans += countTwoPart(sum, l, mid, mid + 1, r, lower, upper);int k = l, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if (p2 > r || (p1 <= mid && sum[p1] < sum[p2])) {temp[k++] = sum[p1++];} else {temp[k++] = sum[p2++];}}for (int i = l; i <= r; i++) sum[i] = temp[i];return ans; }vector<long long> temp;int countRangeSum(vector<int>& nums, int lower, int upper) {vector<long long> sum(nums.size() + 1);while (temp.size() < sum.size()) temp.push_back(0);sum[0] = 0;for (int i = 0; i < nums.size(); i++) sum[i + 1] = sum[i] + nums[i];return mergeSort(sum, 0, sum.size() - 1, lower, upper);}
};

本質(zhì)上還是利用了分治的思想。核心的過程就是如何計(jì)算跨左右兩半部分的過程

315. 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù) - 力扣（LeetCode）

已經(jīng)求得左右半邊各自比它小的元素。兩個(gè)區(qū)間合并。

class Solution {
public:// 歸并排序的思想：分兩個(gè)區(qū)間，統(tǒng)計(jì)兩個(gè)區(qū)間的性質(zhì)。// 在歸并的過程中，左右兩個(gè)有序區(qū)間，合并的時(shí)候，從大到小的順序排，左邊區(qū)間內(nèi)，如果元素大于右邊，則左邊的元素比他小的個(gè)數(shù)應(yīng)當(dāng)加上右邊r-p2+1struct Data {Data(int val, int ind) : val(val), ind(ind), cnt(0) {}bool operator > (const Data &a) {return val > a.val;}int val, ind, cnt;};void mergeSort(vector<Data> &arr, int l, int r) {if (l >= r) return ; // 如果只剩下一個(gè)元素，那就計(jì)算不了左右兩邊的統(tǒng)計(jì)性質(zhì)int mid = (l + r) >> 1;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);int k = l, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if (p2 > r || (p1 <= mid && arr[p1] > arr[p2])) {arr[p1].cnt += r - p2 + 1;temp[k++] = arr[p1++];} else {temp[k++] = arr[p2++];}}for (int i = l; i <= r; i++) arr[i] = temp[i];return ;}vector<Data> temp;vector<int> countSmaller(vector<int>& nums) {vector<Data> arr;for (int i = 0; i < nums.size(); i++) arr.push_back(Data{nums[i], i});while (temp.size() < nums.size()) temp.push_back(Data{0, 0});mergeSort(arr, 0, arr.size() - 1);vector<int> ret(nums.size());for (auto x : arr) ret[x.ind] = x.cnt;return ret;}
};