本次我們來談一下排序算法中的歸并排序算法
首先我們來了解一下歸并排序的思想：分治法甚亭；
分治即分而治之白对，當(dāng)我們面對一個較大規(guī)模的問題時禀综，想要對這個問題直接求解简烘，發(fā)現(xiàn)十分困難苔严，我們發(fā)現(xiàn)，這個大問題能分解成若干個很容易求解的小問題孤澎，而這些小問題在被解決的同時届氢，原問題也得以求解。我們將一個較大規(guī)模問題逐步分解成若干個小問題求解的思想覆旭，就是分治法退子，同時也是遞歸思想。
歸并排序算法就是利用了這種思想型将。
例如：有一列無序數(shù)據(jù)集寂祥，我們想要對該數(shù)據(jù)集進(jìn)行排序，顯然我們似乎無法找到一種很顯而易見的方式做到茶敏，尤其是當(dāng)數(shù)據(jù)規(guī)模很大時壤靶，問題就變得更為困難。我們理想中的解決方式是如果能直接觀察就能得到結(jié)果惊搏，那就再好不過了贮乳。顯然，我們做不到這一點恬惯，根本原因是數(shù)據(jù)太多向拆。我們的想法是，若數(shù)據(jù)少一點酪耳，是不是會好很多呢浓恳？于是我們將數(shù)據(jù)集嘗試性的一分為二來看看。
如上圖碗暗，我們得到了兩個原來數(shù)據(jù)的規(guī)模一半的數(shù)據(jù)集颈将，如果這兩個數(shù)據(jù)集都是有序該多好啊。如下圖：
因為如果是這樣言疗，則原問題就轉(zhuǎn)換成了將兩個有序的數(shù)據(jù)集合并成一個有序的數(shù)據(jù)集的問題晴圾。我們發(fā)現(xiàn)對于這個問題，我們還是很容易做到的噪奄。這就好比我們平常玩的撲克牌死姚，舉個例子：桌子上有兩副有序的牌，我們想要將它合并成一副有序的牌勤篮，我們該怎么做呢都毒？很簡單，假設(shè)兩副牌都是小到大的排放碰缔，小的在上面账劲，首先，我們從兩副牌的頂端，各取一個涤垫，然后比較誰大誰小姑尺，我們將較小的留在手里竟终，而大的放回原位置不動蝠猬，然后重復(fù)此過程，直到其中的一副牌全部比完统捶，或者兩副牌同時比完榆芦。如果其中的一副牌先比完了，則剩下的另一副牌也就沒不用比了喘鸟，直接全部放入手中就行了匆绣。此時，手中的牌就是合并好后的有序的牌了什黑。
代碼實現(xiàn)如下：
void merge(vector<int> &array1, vector<int> &array2, vector<int> &tmp) {
int leftIndex = 0, rightIndex = 0, tmpIndex = 0;
while (leftIndex < array1.size() && rightIndex < array2.size()) {
if (array1[leftIndex] < array2[rightIndex]) {
tmp[tmpIndex++] = array1[leftIndex++];
} else {
tmp[tmpIndex++] = array2[leftIndex++];
}
}
while (leftIndex < array1.size()) {
tmp[tmpIndex++] = array1[leftIndex++];
}
while (rightIndex <= array2.size()) {
tmp[tmpIndex++] = array2[rightIndex++];
}
}
這個問題解決了崎淳，我們似乎還有一個比較頭疼的問題，那就是這兩個數(shù)據(jù)集有序愕把，是我們假設(shè)的條件拣凹，那么我們進(jìn)一步的問題就變成了如何將這兩個子數(shù)據(jù)集進(jìn)行排序的問題。我們發(fā)現(xiàn)恨豁，這個問題和原問題相比似乎沒啥分別嚣镜，只不過是數(shù)據(jù)規(guī)模小了一半而已。是不是可以嘗試將這兩個數(shù)據(jù)集各自再一分為二橘蜜，拆分成更小的數(shù)據(jù)集菊匿，如果我們運氣比較好，這些子數(shù)據(jù)集剛好是有序的计福，那么問題不就解決了嗎跌捆？是的，確實存在這種可能象颖，但是我們不能將問題的解決方式寄托于運氣佩厚，我們可以一直拆分下去，但是我們始終要面臨的一個問題是:拆分到什么程度才能直接確定這些數(shù)據(jù)集的有序性力麸？答案顯而易見可款，當(dāng)數(shù)據(jù)集中只有一個數(shù)時，則該數(shù)據(jù)集肯定是有序的克蚂。
看到上圖的圖示闺鲸，我們應(yīng)該豁然開朗了很多，直接上代碼了
void mergeSort(vector<int> &nums, vector<int> &tmp, int left, int right) {
if (left == right)
return;
int mid = (left + right) / 2;
mergeSort(nums, tmp, left, mid);
mergeSort(nums, tmp, mid, right);
merge(nums, tmp, left, mid, right);
}
void merge(vector<int> &nums, vector<int> &tmp, int left, int mid, int right) {
int leftIndex = left;
int rightIndex = mid + 1;
int tmpIndex = 0;
if (leftIndex <= mid && rightIndex <= right) {
if (nums[leftIndex] < nums[rightIndex]) {
tmp[tmpIndex++] = nums[leftIndex++];
} else {
tmp[tmpIndex++] = nums[leftIndex++];
}
}
while (leftIndex <= mid) {
tmp[tmpIndex++] = nums[leftIndex++];
}
while (rightIndex <= right) {
tmp[tmpIndex++] = nums[rightIndex++];
}
tmpIndex = 0;
while (left <= right) {
nums[left++] = tmp[tmpIndex++];
}
}
