前言¶
本章介紹使用Python實現場景的幾種排序算法。分別有冒泡算法、快速排序、插入排序、希爾排序、選擇排序、堆排序、歸併排序、計數排序、桶排序、基數排序。
創建一個比較大的list，用於測試排序算法使用。
import numpy as np
import time
src_list = np.random.randint(1, 10000000, (100000)).tolist()
冒泡排序¶
冒泡排序是一種簡單直觀的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因爲越小的元素會經由交換慢慢”浮”到數列的頂端。
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(0, n-1-i):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
start = time.time()
result = bubble_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
快速排序¶
在一個數據集中取個數作爲參考點，大於該數的元素放在其右邊；小於該數的元素放在其左邊。這樣就將數據集分成兩部分，大於參考值部分和小於參考值部分，遞歸該過程，直到序列中所有記錄均有序。
def quick_sort(listt, left, right):
if left >= right:
return listt
# 選擇參考點，該調整範圍的第1個值
pivot = listt[left]
low = left
high = right
while left < right:
# 從右邊開始查找大於參考點的值
while left < right and listt[right] >= pivot:
right -= 1
# 這個位置的值先挪到左邊
listt[left] = listt[right]
# 從左邊開始查找小於參考點的值
while left < right and listt[left] <= pivot:
left += 1
# 這個位置的值先挪到右邊
listt[right] = listt[left]
# 寫回改成的值
listt[left] = pivot
# 遞歸，並返回結果
quick_sort(listt, low, left - 1) # 遞歸左邊部分
quick_sort(listt, left + 1, high) # 遞歸右邊部分
return listt
start = time.time()
result = quick_sort(src_list, 0, 1000)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
插入排序¶
插入排序是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入
def insert_sort(alist):
length = len(alist)
for i in range(1,length):
for j in range(i, 0, -1):
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[i]
else:
break
return alist
start = time.time()
result = insert_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
希爾排序¶
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。希爾排序的基本思想是：先將整個待排序的記錄序列分割成爲若干子序列分別進行直接插入排序，待整個序列中的記錄”基本有序”時，再對全體記錄進行依次直接插入排序。
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap >= 1:
for i in range(gap,n):
while (i - gap) >= 0:
if alist[i] < alist[i-gap]:
alist[i], alist[i-gap] = alist[i-gap], alist[i]
i = i - gap
else:
break
gap = gap // 2
return alist
start = time.time()
result = shell_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
選擇排序¶
選擇排序是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
def select_sort(alist):
n = len(alist)
for i in range(n):
# 設置索引 i爲最小值的索引
min_idx = i
# 通過比較，不斷調整最小值的索引位置
for j in range(i,n):
if alist[j] < alist[min_idx]:
min_idx = j
# 交換第i個值與最小值
alist[i], alist[min_idx] = alist[min_idx], alist[i]
return alist
start = time.time()
result = select_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
堆排序¶
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。
# 調整堆的結構，使其父節點的值大於子節點的值
def max_heap(heap, heapsize, root):
left = 2*root+1
right = left + 1
large = root
if left < heapsize and heap[large] < heap[left]:
large = left
if right < heapsize and heap[large] < heap[right]:
large = right
# 若large=right或large=left，則說明，出現比父節點大的子節點，這時對調，使子節點變爲父節點
if large != root:
heap[large], heap[root] = heap[root], heap[large]
max_heap(heap, heapsize, large)
# 構造一個堆，對堆中數據重新排序
def build_max_heap(heap):
length = len(heap)
# 從後往前調整結構
for i in range((length-2)//2,-1,-1):
max_heap(heap, length, i)
# 將根節點取出與最後一位對調，對前面len-1個節點繼續進行對調過程
def heap_sort(heap):
build_max_heap(heap)
for i in range(len(heap)-1,-1,-1):
heap[0], heap[i] = heap[i], heap[0]
max_heap(heap,i,0)
return heap
start = time.time()
result = heap_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
歸併排序¶
歸併排序(mergesort)是創建在歸併操作上的一種有效的排序算法，該算法是採用分治法的一個非常典型的應用。
分治法：
分割：遞歸地把當前序列平均分割成兩半
集成：在保持元素順序的同時將上一步得到的子序列集成到一起(歸併)
def merge_sort(alist):
if len(alist) < 2:
return alist
# 將列表分成更小的兩個列表
mid = int(len(alist)/2)
# 分別對左右兩個列表進行處理，分別返回兩個排序好的列表
left = merge_sort(alist[:mid])
right = merge_sort(alist[mid:])
# 對排序好的兩個列表合併，產生一個新的排序好的列表
return merge(left,right)
def merge(left,right):
i = 0
j = 0
result = []
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
result += left[i:]
result += right[j:]
return result
start = time.time()
result = merge_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
計數排序¶
計數排序的核心在於將輸入的數據值轉化爲鍵存儲在額外開闢的數組空間中。作爲一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。
對每一個輸入的元素a[i]，確定小於 a[i] 的元素個數。所以可以直接把 a[i] 放到它輸出數組中的位置上。假設有5個數小於 a[i]，所以 a[i] 應該放在數組的第6個位置上
def count_sort(alist):
# 找到最大最小值
min_num = min(alist)
max_num = max(alist)
# 初始化計數列表
count_list = [0]*(max_num-min_num+1)
# 對列表中的每一個元素計數
for num in alist:
count_list[num-min_num] += 1
alist.clear()
# 當某個元素的個數不爲 0，將該元素填回alist列表
for cur_num, count in enumerate(count_list):
while count != 0:
alist.append(cur_num+min_num)
count -= 1
return alist
start = time.time()
result = count_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
桶排序¶
把數組a劃分爲n個大小相同子區間（桶），每個子區間各自排序，最後合併。桶排序要求數據的分佈必須均勻，不然可能會失效。計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶裏只有一個元素的情況。
原理：
(1) 設置一個定量的數組當作空桶
(2) 遍歷輸入數據，並且把數據一個一個放到對應的桶裏去
(3) 對每個不是空的桶進行排序
(4) 從不是空的桶裏把排好序的數據拼接起來
def bucket_sort(alist):
min_num = min(alist)
max_num = max(alist)
# 設置桶的大小
bucket_size = (max_num - min_num)/len(alist)
# 創建桶數組
bucket_list = [[]for i in range(len(alist)+1)]
# 向桶數組填數
for num in alist:
bucket_list[int((num-min_num)//bucket_size)].append(num)
alist.clear()
# 回填，這裏桶內部排序直接調用了sorted
for i in bucket_list:
for j in sorted(i):
alist.append(j)
return alist
start = time.time()
result = bucket_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
基數排序¶
基數排序的總體思路就是將待排序數據拆分成多個關鍵字進行排序，也就是說，基數排序的實質是多關鍵字排序，比如說成績的排序，如果兩個人總分相同，則語文高的排在前面，語文成績也相同則數學高的排在前面，如果對數字進行排序，那麼個位、十位、百位就是不同優先級的關鍵
原理：
(1) 取得數組中的最大數，並取得位數
(2) 建立桶數組
(3) 按位數的大小分別裝進不同的桶裏
(4) 將原數組清空，將各個桶裏的數據依次添加進原列表
(5) 再進行前一位的排序，依次循環，直到排序的位數大於最大值的位數
def radix_sort(alist):
# 記錄正在對哪一位進行排序，最低位爲個位
i = 0
# 最大值的位數
max_num = max(alist)
j = len(str(max_num))
while i < j:
# 建立桶數組，數字爲0-9，所以建10個桶
bucket_list = [[]for i in range(10)]
# 按位數的大小分別裝進不同的桶裏
for num in alist:
bucket_list[int(num/(10**i)%10)].append(num)
#將原列表清空，將各個桶裏的數據依次添加進原列表
alist.clear()
for l in bucket_list:
for b in l:
alist.append(b)
# 再進行前一位的排序，依次循環，直到排序的位數大於最大值的位數
i += 1
return alist
start = time.time()
result = radix_sort(src_list)
end = time.time()
print ("耗時：%d 毫秒" % int(round((end - start) * 1000)))
更好閱讀體驗可以訪問Kesci Lab： https://www.kesci.com/home/project/5ebf61f52d8821002dc425d0