Merge Sort
該課程前面幾節(jié)課作為入門, 所以會介紹一些算法, 但后面會有更扎實瑟匆、底層諸如復雜度分析等內(nèi)容.
按講者說法, 這種算法還是比較實際引用廣泛的, 我后來稍微google了一下, 說這種算法最壞最好情況都是一樣的時間復雜度.
思想很簡單, 屬于Divide and Conquer , 就是遞歸的把它二分打散, 再用O(N)的函數(shù)把它們merge起來. 下面的代碼是不去重的, 即有重復數(shù)字仍然包含在內(nèi).
def merge_sorted_lists(a, b):
res = []
# init indices for a, b
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
res.append(a[i])
i = i + 1
else:
res.append(b[j])
j = j + 1
if i < len(a):
res = res + a[i:]
else:
res = res + b[j:]
return res
def merge_sort(l):
# THIS IS for exit!!!
if len(l) <= 1:
return l
a = l[:int(len(l)/2)]
b = l[int(len(l)/2):]
left = merge_sort(a)
right = merge_sort(b)
return merge_sorted_lists(left, right)
if __name__ == '__main__':
l = [4,5,7,9,7,5,1,0,7,-2,3,-99,6]
print(merge_sort(l))
在度量其復雜度時, 講者采用的是recursive tree, 其實就是笨辦法, 把遞歸過程全部列出來, 計算每一層級需要的代價. 在第j (j=0,1,2,...,logN)層, 有2^j子問題(就是需要merge的)宴合， 每個子問題的size是(至多)需要6(N/(2^j))的代價(代碼行數(shù)). 因此, 不管在哪一層, 代價都是6N, 所以最多就是6N(1+logN).
