直接插入排序
時間復雜度：O(n2)
空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
算法思想：假設待排序的數據是數組A[1….n]尺迂。初始時，A[1]自成1個有序區(qū)冒掌，無序區(qū)為A[2….n]噪裕。在排序的過程中，依次將A[i] (i=2,3,….,n)從后往前插入到前面已排好序的子數組A[1,…,i-1]中的適當位置股毫，當所有的A[i] 插入完畢膳音，數組A中就包含了已排好序的輸出序列。
def insert_sort(array): # 定義直接插入排序的函數铃诬，將需要排序的數組作為形參
for i in range(len(array)): # 從頭依次循環(huán)祭陷，并取循環(huán)坐標作為下一循環(huán)的節(jié)點
for j in range(i): # 從頭開始，循環(huán)到第一循環(huán)循環(huán)到的數為止
if array[i] > array[j]: # 判斷第一循環(huán)坐標的值是否大于第二循環(huán)坐標的值
array.insert(j, array.pop(i)) # 判斷結果為真則將值小的數置前
return array # 返回排好序之后的數組
希爾排序
時間復雜度：O(n)
空間復雜度：O(n√n)
穩(wěn)定性：不穩(wěn)定
算法思想：希爾排序是把記錄按下標的一定增量分組趣席，對每組使用直接插入排序算法排序兵志；隨著增量逐漸減少，每組包含的關鍵詞越來越多吩坝，當增量減至1時毒姨，整個文件恰被分成一組，算法便終止钉寝。
def shell_sort(array):
gap = len(array) # 設置增量
while gap > 1:
gap = gap // 2 # 選擇增量弧呐，當所有的數被分為一組的時候即退出循環(huán)
for i in range(gap, len(array)): # 分組
for j in range(i % gap, i, gap): # 設置增量為步進，實現(xiàn)比較每組數大小的效果
if array[i] < array[j]: # 判斷后將數值小的數組元素置前
array[i], array[j] = array[j], array[i]
return array
簡單選擇排序
時間復雜度：O(n2)
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
算法思想：每一趟從待排序的數據元素中選擇最星陡佟（或最大）的一個元素作為首元素俘枫，直到所有元素排完為止，簡單選擇排序是不穩(wěn)定排序逮走。
def select_sort(array):
for i in range(len(array)): # 每取一個值鸠蚪，可以看做是一趟
x = i # min index
for j in range(i, len(array)): # 遍歷數組，與取出的元素進行比較
if array[j] < array[x]: # 取當前趟次最小元素，置于已經遍歷過的數據之前
x = j
array[i], array[x] = array[x], array[i]
return array
堆排序
時間復雜度：O(nlog?n)
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
算法思想：將待排序序列構造成一個大頂堆茅信，此時盾舌，整個序列的最大值就是堆頂的根節(jié)點。將其與末尾元素進行交換蘸鲸，此時末尾就為最大值妖谴。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值酌摇。如此反復執(zhí)行膝舅，便能得到一個有序序列了。
def heap_sort(array):
def heap_adjust(parent): # 構造初始堆并比較近似完全二叉樹中節(jié)點的值
child = 2 * parent + 1 # 左孩子節(jié)點
while child < len(heap):
if child + 1 < len(heap):
if heap[child + 1] > heap[child]:
child += 1 # 右孩子節(jié)點
if heap[parent] >= heap[child]: # 父節(jié)點大于右孩子節(jié)點便結束循環(huán)
break
heap[parent], heap[child] = heap[child], heap[parent] # 交換左孩子節(jié)點與父節(jié)點的值窑多，使大數后沉
parent, child = child, 2 * child + 1
heap, array = array.copy(), []
for i in range(len(heap) // 2, -1, -1):
heap_adjust(i)
while len(heap) != 0: # 使所有的數都經過比較
heap[0], heap[-1] = heap[-1], heap[0]
array.insert(0, heap.pop())
heap_adjust(0)
return array
https://blog.csdn.net/MoreWindows/article/details/6709644
http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html
https://www.cnblogs.com/chengxiao/p/6129630.html
http://images.cnblogs.com/cnblogs_com/kkun/201111/201111301912294099.gif
冒泡排序
時間復雜度：O(n2)
空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
算法思想：對相鄰的元素進行兩兩比較仍稀，順序相反則進行交換，這樣埂息，每一趟會將最小或最大的元素“浮”到頂端技潘，最終達到完全有序。
def bubble_sort(array):
for i in range(len(array)):
for j in range(i, len(array)):
if array[i] > array[j]: # 若前面的數大于后面的數耿芹，則交換位置
array[i], array[j] = array[j], array[i]
return array
快速排序
時間復雜度：O(nlog?n)
空間復雜度：O(nlog?n)
穩(wěn)定性：不穩(wěn)定
算法思想：通過一趟排序將要排序的數據分割成獨立的兩部分崭篡，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序吧秕，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列迹炼。
def quick_sort(array):
def recursive(begin, end):
if begin > end:
return
l, r = begin, end
pivot = array[l] # 定義標準砸彬，也就是本次執(zhí)行結束之后找到自己位置的那個數
while l < r: # 利用while循環(huán)從開始到結尾依次與標準比較
while l < r and array[r] > pivot: # 比標準大的數，放到右邊
r -= 1
while l < r and array[l] <= pivot: # 比標準小的數斯入，放到左邊
l += 1
array[l], array[r] = array[r], array[l] # 若不滿足上述條件砂碉，左右調換
array[l], array[begin] = pivot, array[l] # 標準找到自己位置
recursive(begin, l - 1) # 左邊調用，即：對比已經找到位置的數小的數進行排序
recursive(r + 1, end) # 右邊調用刻两，即：對比已經找到位置的數大的數進行排序
recursive(0, len(array) - 1) # 調用一次方法增蹭，一個數找到正確位置，下次參與排序的數-1
return array
http://www.cnblogs.com/foreverking/articles/2234225.html
歸并排序
時間復雜度：O(nlog?n)
空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
算法思想：是創(chuàng)建在歸并操作上的一種有效的排序算法磅摹，效率為O(n log n)滋迈。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用户誓，且各層分治遞歸可以同時進行饼灿。(先分后治再合并)
def merge_sort(array):
def merge_arr(arr_l, arr_r): # 先治后合
array = []
while len(arr_l) and len(arr_r): # 治
if arr_l[0] <= arr_r[0]: # 右邊的組數大，就添加左邊的數到下一組
array.append(arr_l.pop(0)) # 判斷一個帝美，取出一個碍彭，直到全部取完
elif arr_l[0] > arr_r[0]: # 左邊的組數大，就添加右邊的數到下一組
array.append(arr_r.pop(0))
if len(arr_l) != 0: # 合
array += arr_l # 合左邊
elif len(arr_r) != 0:
array += arr_r # 合右邊
return array
def recursive(array): # 分
if len(array) == 1: # 分到最小單位
return array
mid = len(array) // 2 # 對二取整，切片劃分數組
arr_l = recursive(array[:mid])
arr_r = recursive(array[mid:])
return merge_arr(arr_l, arr_r) # 一分為二
return recursive(array)
https://www.cnblogs.com/chengxiao/p/6194356.html
基數排序
時間復雜度：O(d(r+n))
空間復雜度：O(rd+n)
穩(wěn)定性：穩(wěn)定
算法思想：將整數按位數切割成不同的數字庇忌，然后按每個位數分別比較舞箍。
def radix_sort(array):
bucket, digit = [[]], 0 # 初始化桶數組和數位控制
while len(bucket[0]) != len(array): # 判斷是否將所有位數取出
bucket = [[], [], [], [], [], [], [], [], [], []] # 設置桶數組
for i in range(len(array)):
num = (array[i] // 10 ** digit) % 10 # 取當前位數
bucket[num].append(array[i]) # 放入相應的桶中
array.clear() # 清楚當前數據
for i in range(len(bucket)):
array += bucket[i] # 將排好序的桶數組添加進數組
digit += 1 # 數位控制
return array
https://www.cnblogs.com/skywang12345/p/3603669.html
