科技

史上最簡單的python演算法入門書，像看小說一樣學習演算法你敢信？

演算法 Python · 發表 2019-04-07 10:02:26

摘要：演算法是電腦科學領域最重要的基石之一，同時也是出了名地難學。最出名的一本書莫過於演算法導論了但是，這本非常非常出名的大頭書，真的是誰看誰知道。看了之後都有點懷疑人生，一大批人也因此從入門到放棄。但是還是有很多人跑去學演算法，為什麼呢？ ...

演算法是電腦科學領域最重要的基石之一，同時也是出了名地難學。最出名的一本書莫過於演算法導論了

但是，這本非常非常出名的大頭書，真的是誰看誰知道。看了之後都有點懷疑人生，一大批人也因此從入門到放棄。

但是還是有很多人跑去學演算法，為什麼呢？

原因還是演算法工程師的待遇實在是太好了，做技術崗位的都能達到月薪三萬，如果再會點業務做管理呢？想都不敢想哦。

其實演算法真的難嗎？其實不然。如果你覺得難得話，那肯定是因為你沒有看過這本書

號稱能像看小說一樣看懂演算法。我一開始也是不信的，畢竟我可是看過演算法導論的人。因為是圖靈出版社（國內最好的IT類書籍出版社）出版的書籍，所以我還是買來看了一下，結果就真的就像是看小說一樣，花了一天時間全部看完了。我們也可以看一下別人的評論。

我自己是看過這本書的，所以我對上面的評論也深信不疑。由於好評太多了，我就不一一展示了，想要詳細瞭解的可以去看一下豆瓣評論。接下來我們看一下部分內容。

內容部分

一、演算法簡介

1.1二分查詢：

一個有序陣列中找一個數的位置（對應該數字所在陣列下標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

也可用遞迴實現

操作物件：陣列

使用前提：有序的陣列

效能方面：時間複雜度O(logn)

1.2 旅行商問題：

旅行商前往n個城市，確保旅程最短。求可能的排序：n!種可能。

二、選擇排序

2.1 陣列和連結串列

陣列：連續儲存在硬碟中；連結串列：分散儲存在硬碟中；

2.2 選擇排序：將陣列元素按照從小到大的順序排序，每次從陣列中取出最小值

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]

三、遞迴----一種優雅的問題解決方法

適用遞迴的演算法要滿足：

基限條件（即返回的條件）

遞迴條件（呼叫遞迴函式）

特點：

自己呼叫自己，呼叫棧在記憶體疊加，如果沒有返回條件，將無限迴圈呼叫，佔用大量記憶體，最終爆棧終止程序。

還有一種高階一點的遞迴：

尾遞迴（將結果也放入函式引數，記憶體裡面呼叫棧只有一個當前執行的函式程序）

舉個簡單的例子：階乘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

四、快速排序（分而治之策略）

每次選取陣列中一個元素x當作分水嶺（一般選取第一個元素）：[小於元素x的陣列]+[x]+[大於元素x的陣列]，然後遞迴呼叫，直到最後處理的陣列元素只剩下零個或者一個

平均時間複雜度O(nlogn)

最差情況時間複雜度O(n^2) (出現這個情況是：快排的陣列本來就是有序的（順序/倒序），選取的元素又是開頭第一個的話，每次變成只能處理一側的陣列了。改善：可以選取陣列中間的元素當作分水嶺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]
'''

到目前演算法為止，複雜度對比：

排序到演算法有：

氣泡排序，選擇排序，快速排序，歸併排序，堆排序（感興趣到小夥伴可以自己去搜索）

下面列出氣泡排序和歸併排序演算法：

#氣泡排序，每次尋找最小到元素往前排，就像汽水從下往上冒一樣。所以叫氣泡排序啦

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]

氣泡排序時間複雜度O(n^2)

兩個for迴圈搞定，每一輪for迴圈找到一個最小值。for迴圈兩兩元素對比交換

歸併排序：

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): #並兩個已排序好的列表，產生一個新的已排序好的列表
result = [] # 新的已排序好的列表
i = 0 # 下標
j = 0
# 對兩個列表中的元素 兩兩對比
# 將最小的元素，放到result中，並對當前列表下標加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其中一個已經新增完畢，剩下的就全部加到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]

歸併排序時間複雜度是O(nlogn)

最壞情況也是O(nlogn)

後面還有很多，我就不一一列舉了。這本書將深奧的知識用通俗易懂的語言表達出來，同時加上生動形象的配圖，看了的都說好。

最後，學習Python中的小夥伴，需要學習資料的話，可以前往我的微信公眾號：速學Python，後臺回覆：簡書，即可拿Python學習資料

這裡有我自己整理了一套最新的python系統學習教程，包括從基礎的python指令碼到web開發、爬蟲、資料分析、資料視覺化、機器學習等。送給正在學習python的小夥伴！這裡是python學習者聚集地，歡迎初學和進階中的小夥伴！

來源：簡書

史上最簡單的python演算法入門書，像看小說一樣學習演算法你敢信？

您可能也會喜歡…