現(xiàn)在很多的事情都可以用算法來解決胸哥，在編程上橘忱，算法有著很重要的地位赴魁，將算法用函數(shù)封裝起來，使程序能更好的調用钝诚，不需要反復編寫尚粘。
Python十大經典算法：
一、插入排序
- 算法思想
從第二個元素開始和前面的元素進行比較敲长，如果前面的元素比當前元素大郎嫁，則將前面元素 后移，當前元素依次往前祈噪，直到找到比它小或等于它的元素插入在其后面泽铛，然后選擇第三個元素，重復上述操作辑鲤，進行插入盔腔，依次選擇到最后一個元素，插入后即完成所有排序月褥。 - 代碼實現(xiàn)
def insertion_sort(arr):
#插入排序
# 第一層for表示循環(huán)插入的遍數(shù)
for i in range(1, len(arr)):
# 設置當前需要插入的元素
current = arr[i]
# 與當前元素比較的比較元素
pre_index = i - 1
while pre_index >= 0 and arr[pre_index] > current:
# 當比較元素大于當前元素則把比較元素后移
arr[pre_index + 1] = arr[pre_index]
# 往前選擇下一個比較元素
pre_index -= 1
# 當比較元素小于當前元素弛随，則將當前元素插入在 其后面
arr[pre_index + 1] = current
return arr
二、選擇排序
- 算法思想
設第一個元素為比較元素宁赤，依次和后面的元素比較舀透，比較完所有元素找到最小的元素，將它和第一個元素互換决左，重復上述操作愕够，我們找出第二小的元素和第二個位置的元素互換，以此類推找出剩余最小元素將它換到前面佛猛，即完成排序惑芭。 - 代碼實現(xiàn)
def selection_sort(arr):
#選擇排序
# 第一層for表示循環(huán)選擇的遍數(shù)
for i in range(len(arr) - 1):
# 將起始元素設為最小元素
min_index = i
# 第二層for表示最小元素和后面的元素逐個比較
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果當前元素比最小元素小，則把當前元素角標記為最小元素角標
min_index = j
# 查找一遍后將最小元素與起始元素互換
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr
三继找、冒泡排序
- 算法思想
從第一個和第二個開始比較遂跟，如果第一個比第二個大，則交換位置婴渡，然后比較第二個和第三個幻锁，逐漸往后，經過第一輪后最大的元素已經排在最后缩搅，所以重復上述操作的話第二大的則會排在倒數(shù)第二的位置越败。，那重復上述操作n-1次即可完成排序硼瓣，因為最后一次只有一個元素所以不需要比較究飞。 - 代碼實現(xiàn)
def bubble_sort(arr):
#冒泡排序
# 第一層for表示循環(huán)的遍數(shù)
for i in range(len(arr) - 1):
# 第二層for表示具體比較哪兩個元素
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
# 如果前面的大于后面的置谦，則交換這兩個元素的位置
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
四、快速排序
- 算法思想
找出基線條件亿傅，這種條件必須盡可能簡單媒峡，不斷將問題分解（或者說縮小規(guī)模），直到符合基線條件葵擎。 - 代碼實現(xiàn)
def quick_sort(arr):
if len(arr) < 2:
# 基線條件：為空或只包含一個元素的數(shù)組是“有序”的
return arr
else:
# 遞歸條件
pivot = arr[0]
# 由所有小于基準值的元素組成的子數(shù)組
less = [i for i in arr[1:] if i <= pivot]
# 由所有大于基準值的元素組成的子數(shù)組
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quick_sort([10, 5, 2, 3]))
五谅阿、歸并排序
- 算法思想
歸并排序是分治法的典型應用。分治法（Divide-and-Conquer）：將原問題劃分成 n 個規(guī)模較小而結構與原問題相似的子問題酬滤；遞歸地解決這些問題签餐，然后再合并其結果，就得到原問題的解盯串，分解后的數(shù)列很像一個二叉樹氯檐。
具體實現(xiàn)步驟：
1.使用遞歸將源數(shù)列使用二分法分成多個子列
2.申請空間將兩個子列排序合并然后返回
3.將所有子列一步一步合并最后完成排序
注：先分解再歸并
- 代碼實現(xiàn)
def merge_sort(arr):
#歸并排序
if len(arr) == 1:
return arr
# 使用二分法將數(shù)列分兩個
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 使用遞歸運算
return marge(merge_sort(left), merge_sort(right))
def marge(left, right):
#排序合并兩個數(shù)列
result = []
# 兩個數(shù)列都有值
while len(left) > 0 and len(right) > 0:
# 左右兩個數(shù)列第一個最小放前面
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
# 只有一個數(shù)列中還有值，直接添加
result += left
result += right
return result
六体捏、希爾排序
- 算法思想
希爾排序的整體思想是將固定間隔的幾個元素之間排序冠摄，然后再縮小這個間隔。這樣到最后數(shù)列就成為了基本有序數(shù)列几缭。
具體步驟：
1.計算一個增量（間隔）值
2.對元素進行增量元素進行比較河泳，比如增量值為7，那么就對0,7,14,21…個元素進行插入排序
3.然后對1,8,15…進行排序年栓，依次遞增進行排序
4.所有元素排序完后拆挥，縮小增量比如為3，然后又重復上述第2韵洋，3步
5.最后縮小增量至1時竿刁，數(shù)列已經基本有序黄锤，最后一遍普通插入即可
- 代碼實現(xiàn)
def shell_sort(arr):
#希爾排序
# 取整計算增量（間隔）值
gap = len(arr) // 2
while gap > 0:
# 從增量值開始遍歷比較
for i in range(gap, len(arr)):
j = i
current = arr[i]
# 元素與他同列的前面的每個元素比較搪缨，如果比前面的小則互換
while j - gap >= 0 and current < arr[j - gap]:
arr[j] = arr[j - gap]
j -= gap
arr[j] = current
# 縮小增量（間隔）值
gap //= 2
return arr
七、基數(shù)排序
- 算法思想
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort）鸵熟，又稱“桶子法”（bucket sort）或bin sort副编，顧名思義，它是透過鍵值的部份資訊流强，將要排序的元素分配至某些“桶”中痹届，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序打月，其時間復雜度為O (nlog(r)m)队腐，其中r為所采取的基數(shù)，而m為堆數(shù)奏篙，在某些時候柴淘，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法迫淹。 - 代碼實現(xiàn)
2.1由桶排序改造，從最低位到最高位依次桶排序为严，最后輸出最后排好的列表敛熬。
def RadixSort(list,d):
for k in range(d):#d輪排序
# 每一輪生成10個列表
s=[[] for i in range(10)]#因為每一位數(shù)字都是0~9，故建立10個桶
for i in list:
# 按第k位放入到桶中
s[i//(10**k)%10].append(i)
# 按當前桶的順序重排列表
list=[j for i in s for j in i]
return list
2.2簡單實現(xiàn)
from random import randint
def radix_sort():
A = [randint(1, 99999999) for _ in xrange(9999)]
for k in xrange(8):
S = [ [] for _ in xrange(10)]
for j in A:
S[j / (10 ** k) % 10].append(j)
A = [a for b in S for a in b]
for i in A:
print i
八第股、計數(shù)排序
- 算法思想
對每一個輸入元素x应民，確定小于x的元素個數(shù)。利用這一信息夕吻，就可以直接把x 放在它在輸出數(shù)組上的位置上了诲锹，運行時間為O(n)，但其需要的空間不一定涉馅，空間浪費大辕狰。 - 代碼實現(xiàn)
from numpy.random import randint
def Conuting_Sort(A):
k = max(A) # A的最大值，用于確定C的長度
C = [0]*(k+1) # 通過下表索引控漠，臨時存放A的數(shù)據(jù)
B = (len(A))*[0] # 存放A排序完成后的數(shù)組
for i in range(0, len(A)):
C[A[i]] += 1 # 記錄A有哪些數(shù)字蔓倍，值為A[i]的共有幾個
for i in range(1, k+1):
C[i] += C[i-1] # A中小于i的數(shù)字個數(shù)為C[i]
for i in range(len(A)-1, -1, -1):
B[C[A[i]]-1] = A[i] # C[A[i]]的值即為A[i]的值在A中的次序
C[A[i]] -= 1 # 每插入一個A[i]，則C[A[i]]減一
return B
九盐捷、堆排序
- 算法思想
堆分為最大堆和最小堆偶翅，是完全二叉樹。堆排序就是把堆頂?shù)淖畲髷?shù)取出碉渡，將剩余的堆繼續(xù)調整為最大堆,具體過程在第二塊有介紹聚谁，以遞歸實現(xiàn) ，剩余部分調整為最大堆后,再次將堆頂?shù)淖畲髷?shù)取出滞诺，再將剩余部分調整為最大堆,這個過程持續(xù)到剩余數(shù)只有一個時結束形导。 - 代碼實現(xiàn)
import time,random
def sift_down(arr, node, end):
root = node
#print(root,2*root+1,end)
while True:
# 從root開始對最大堆調整
child = 2 * root +1 #left child
if child > end:
#print('break',)
break
print("v:",root,arr[root],child,arr[child])
print(arr)
# 找出兩個child中交大的一個
if child + 1 <= end and arr[child] < arr[child + 1]: #如果左邊小于右邊
child += 1 #設置右邊為大
if arr[root] < arr[child]:
# 最大堆小于較大的child, 交換順序
tmp = arr[root]
arr[root] = arr[child]
arr[child]= tmp
# 正在調整的節(jié)點設置為root
#print("less1:", arr[root],arr[child],root,child)
root = child #
#[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]
#print("less2:", arr[root],arr[child],root,child)
else:
# 無需調整的時候, 退出
break
#print(arr)
print('-------------')
def heap_sort(arr):
# 從最后一個有子節(jié)點的孩子還是調整最大堆
first = len(arr) // 2 -1
for i in range(first, -1, -1):
sift_down(arr, i, len(arr) - 1)
#[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
print('--------end---',arr)
# 將最大的放到堆的最后一個, 堆-1, 繼續(xù)調整排序
for end in range(len(arr) -1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(arr, 0, end - 1)
#print(arr)
十、桶排序
- 算法思想
為了節(jié)省空間和時間习霹，我們需要指定要排序的數(shù)據(jù)中最小以及最大的數(shù)字的值朵耕，來方便桶排序算法的運算。 - 代碼實現(xiàn)
#桶排序
def bucket_sort(the_list):
#設置全為0的數(shù)組
all_list = [0 for i in range(100)]
last_list = []
for v in the_list:
all_list[v] = 1 if all_list[v]==0 else all_list[v]+1
for i,t_v in enumerate(all_list):
if t_v != 0:
for j in range(t_v):
last_list.append(i)
return last_list
總結：
在編程中淋叶，算法都是相通的阎曹，算法重在算法思想，相當于將一道數(shù)學上的應用題的每個條件煞檩，區(qū)間处嫌，可能出現(xiàn)的結果進行分解，分步驟的實現(xiàn)它斟湃。算法就是將具體問題的共性抽象出來熏迹，將步驟用編程語言來實現(xiàn)。通過這次對排序算法的整理凝赛，加深了對各算法的了解注暗，具體的代碼是無法記憶的厨剪，通過對算法思想的理解，根據(jù)偽代碼來實現(xiàn)具體算法的編程友存，才是真正了解算法祷膳。
