算法是計算機科學(xué)領(lǐng)域最重要的基石之一，同時也是出了名地難學(xué)。最出名的一本書莫過于算法導(dǎo)論了
但是，這本非常非常出名的大頭書，真的是誰看誰知道?？戳酥蠖加悬c懷疑人生，一大批人也因此從入門到放棄。
但是還是有很多人跑去學(xué)算法，為什么呢？
原因還是算法工程師的待遇實在是太好了，做技術(shù)崗位的都能達到月薪三萬，如果再會點業(yè)務(wù)做管理呢？想都不敢想哦。
其實算法真的難嗎？其實不然。如果你覺得難得話，那肯定是因為你沒有看過這本書
號稱能像看小說一樣看懂算法。我一開始也是不信的，畢竟我可是看過算法導(dǎo)論的人。因為是圖靈出版社（國內(nèi)最好的IT類書籍出版社）出版的書籍，所以我還是買來看了一下，結(jié)果就真的就像是看小說一樣，花了一天時間全部看完了。我們也可以看一下別人的評論。
我自己是看過這本書的，所以我對上面的評論也深信不疑。由于好評太多了，我就不一一展示了，想要詳細了解的可以去看一下豆瓣評論。接下來我們看一下部分內(nèi)容。
內(nèi)容部分
一、算法簡介
1.1二分查找 ：
一個有序數(shù)組中找一個數(shù)的位置（對應(yīng)該數(shù)字所在數(shù)組下標(biāo)index）。
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = int((low + high) / 2)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
print(binary_search(my_list, -1)) # => None
也可用遞歸實現(xiàn)
操作對象：數(shù)組
使用前提：有序的數(shù)組
性能方面：時間復(fù)雜度O(logn)
1.2 旅行商問題：
旅行商前往n個城市，確保旅程最短。求可能的排序：n!種可能。
二、選擇排序
2.1 數(shù)組和鏈表
數(shù)組：連續(xù)存儲在硬盤中；鏈表：分散存儲在硬盤中；
2.2 選擇排序：將數(shù)組元素按照從小到大的順序排序，每次從數(shù)組中取出最小值
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 6, 2, 10])) #[2, 3, 5, 6, 10]
三、遞歸----一種優(yōu)雅的問題解決方法
適用遞歸的算法要滿足：
基限條件（即返回的條件）
遞歸條件（調(diào)用遞歸函數(shù)）
特點：
自己調(diào)用自己，調(diào)用棧在內(nèi)存疊加，如果沒有返回條件，將無限循環(huán)調(diào)用，占用大量內(nèi)存，最終爆棧終止進程。
還有一種高級一點的遞歸：
尾遞歸 （將結(jié)果也放入函數(shù)參數(shù)，內(nèi)存里面調(diào)用棧只有一個當(dāng)前運行的函數(shù)進程）
舉個簡單的例子： 階乘f(n) = n！
def fact(x): #遞歸
if x == 1:
return 1
else:
return x * fact(x-1) #注意這里跟尾遞歸不同
#尾遞歸
def factorial(x,result):
if x == 1:
return result
else:
return factorial(x-1,x*result)
if __name__ == '__main__':
print(fact(5)) #5*4*3*2*1 = 120
print(factorial(5,1)) #120
四、快速排序 （分而治之策略）
每次選取數(shù)組中一個元素x當(dāng)作分水嶺（一般選取第一個元素）：[小于元素x的數(shù)組]+[x]+[大于元素x的數(shù)組]，然后遞歸調(diào)用，直到最后處理的數(shù)組元素只剩下零個或者一個
平均時間復(fù)雜度O(nlogn)
最差情況時間復(fù)雜度O(n^2) (出現(xiàn)這個情況是：快排的數(shù)組本來就是有序的（順序/倒序），選取的元素又是開頭第一個的話，每次變成只能處理一側(cè)的數(shù)組了。 改善：可以選取數(shù)組中間的元素當(dāng)作分水嶺pivot，只有兩邊的元素就都能均勻處理了)
#!/usr/bin/python
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot] #超級像偽代碼！
print(less)
greater = [i for i in array[1:] if i > pivot]
print(greater)
return quicksort(less) + [pivot] + quicksort(greater)
if __name__ == '__main__':
print(quicksort([7,1,10,5,3,2,6]))
'''
[1, 5, 3, 2, 6]
[10]
[]
[5, 3, 2, 6]
[3, 2]
[6]
[2]
[]
[1, 2, 3, 5, 6, 7, 10]
'''
到目前算法為止，復(fù)雜度對比：
排序到算法有：
冒泡排序，選擇排序，快速排序，歸并排序，堆排序（感興趣到小伙伴可以自己去搜索）
下面列出冒泡排序和歸并排序算法：
#冒泡排序，每次尋找最小到元素往前排，就像汽水從下往上冒一樣。所以叫冒泡排序啦
def simpleSort(array):
for i in range(len(array)-1):
for j in range(i,len(array)):
if array[i] > array[j]:
temp = array[i]
array[i] = array[j]
array[j] = temp
return array
print(simpleSort([9,8,6,7,4,5,3,11,2])) #[2, 3, 4, 5, 6, 7, 8, 9, 11]
冒泡排序時間復(fù)雜度O(n^2)
兩個for循環(huán)搞定，每一輪for循環(huán)找到一個最小值。for循環(huán)兩兩元素對比交換
歸并排序：
def mergeSort(array):
if len(array) < 2:
return array
else:
mid = int(len(array)/2)
left = mergeSort(array[:mid])
right = mergeSort(array[mid:])
return merge(left, right)
def merge(left, right): #并兩個已排序好的列表，產(chǎn)生一個新的已排序好的列表
result = [] # 新的已排序好的列表
i = 0 # 下標(biāo)
j = 0
# 對兩個列表中的元素 兩兩對比
# 將最小的元素，放到result中，并對當(dāng)前列表下標(biāo)加1
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 此時left或者right其中一個已經(jīng)添加完畢，剩下的就全部加到result后面即可
result += left[i:]
result += right[j:]
return result
array = [9,5,3,0,6,2,7,1,4,8]
result = mergeSort(array)
print('排序后：',result) #排序后： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
歸并排序時間復(fù)雜度是O(nlogn)
最壞情況也是O(nlogn)
后面還有很多，我就不一一列舉了。這本書將深奧的知識用通俗易懂的語言表達出來，同時加上生動形象的配圖，看了的都說好。
最后，學(xué)習(xí)Python中的小伙伴，需要學(xué)習(xí)資料的話，可以前往我的微信公眾號：速學(xué)Python，后臺回復(fù)：簡書，即可拿Python學(xué)習(xí)資料
這里有我自己整理了一套最新的python系統(tǒng)學(xué)習(xí)教程，包括從基礎(chǔ)的python腳本到web開發(fā)、爬蟲、數(shù)據(jù)分析、數(shù)據(jù)可視化、機器學(xué)習(xí)等。送給正在學(xué)習(xí)python的小伙伴！這里是python學(xué)習(xí)者聚集地，歡迎初學(xué)和進階中的小伙伴！
