我看了下那篇merge sort，已經(jīng)很長了姜凄，所以專門新開一節(jié)來闡述其他實現(xiàn)政溃，包括python實現(xiàn)和c++使用vector（不使用指針和數(shù)組）。
先說python的态秧。
其實我想寫這篇文章就是看到了py的實現(xiàn)董虱，感覺很優(yōu)雅，當然申鱼，沒有上次的quick sort優(yōu)雅愤诱，你不得不承認python的語法糖確實好用，尤其是針對list润讥，dict和set的转锈，我真心覺得python將大部分（除了那些scikit-learn，tensorflow之類的底層輪子）算法工程師從繁瑣的實現(xiàn)中解放了出來楚殿，我一個師兄在百度某nlp部門撮慨，天天看n年前的老舊c++代碼竿痰，幾近崩潰（當然人家肯定要從底層寫起，不可能用tf砌溺，pytouch之類的）影涉。
廢話這么多，我們就寫一下吧：
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) / 2
L = a[:mid]
R = a[mid:]
mergesort[L]
mergesort[R]
return merge(L, R)
def merge(L, R):
tmp = [ ]
i, j = 0, 0
while (i<len(L) and j<len(R)):
if L[i]<R[j]:
tmp.append(L[i])
i += 1
else:
tmp.append(R[j])
j += 1
tmp += L[i:]
tmp += R[j:]
return tmp
調(diào)用的main就這么寫一下：
if __name__ == '__main__':
a = [2, 3, 6, 1, 9, 5, 0]
print merge_sort(a)
其實python的簡潔是不用說的规伐，關鍵一點好的是蟹倾，在這個算法中，merge_sort中由于list索引的良好性質(zhì)猖闪，mid很巧妙地將原list劃分為兩個都是左閉右開的區(qū)間[)鲜棠，這樣的算法就很均衡，自己在紙上寫的時候就很容易判斷正誤培慌。
其實我就是看到了這個豁陆，才想用c++的vector實現(xiàn)一下，我覺得吧吵护，以后stl以及里邊封裝的數(shù)據(jù)結構會是主流盒音，可以說stl+引用將大大減少指針的上場空間。當然馅而，如果以后面試的時候你這樣寫祥诽，我估計問的問題就會從語法細節(jié)變?yōu)椤盀槭裁词莢ector？”瓮恭，“你說stl是主流雄坪，那你講講c++11和17”。信我偎血，問這些大而空的問題要絕對好于糾纏于語法細節(jié)诸衔；而面試的時候，指針的書寫極其容易寫出bug颇玷，大大減分笨农。
那么我們寫一下：
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
void Merge(vector<int>&a, int left, int mid, int right)
{
vector<int> l, r, tmp;
for (int x = left; x < mid; ++x)
l.push_back(a[x]);
for (int x = mid; x < right; ++x)
r.push_back(a[x]);
int x = 0; int y = 0;
while (x < (mid - left)&&y < (right - mid))
if (l[x] <= r[y])
tmp.push_back(l[x++]);
else
tmp.push_back(r[y++]);
while (x<mid-left)
tmp.push_back(l[x++]);
while (y<right-mid)
tmp.push_back(r[y++]);
copy(tmp.begin(), tmp.end(), a.begin() + left);
}
void mergeSort(vector<int> &a, int left, int right)
{
if (right - left <= 1)
return;
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid, right);
Merge(a, left, mid, right);
}
還有一個地方可以修改一下，就是Merge中的tmp的使用帖渠≮艘啵可以直接對a進行操作（引用嘛），不過還需要一點點轉換空郊，我比較懶份招，就不寫了。這樣寫狞甚，避免了我一直很討厭的類似right - mid + 1這些+1-1的瑣事锁摔，統(tǒng)一為左閉右開，十分犀利（#害羞）哼审。
