排序是編程中最為常見的操作之一，也是極為基礎(chǔ)的算法。本節(jié)將快速回顧幾種經(jīng)典的排序方式，并用python實現(xiàn)它們。
為了簡單起見，我們只進行數(shù)字的排序，且統(tǒng)一為從小到大排序。（在實際的python使用中，可以直接用list.sort()函數(shù)完成排序。）
冒泡排序
冒泡排序需要多次遍歷列表。它比較相鄰的項并交換那些無序的項。每次遍歷列表將下一個最大的值放在其正確的位置。
# 冒泡排序
def bubble_sort(num_list):
epochs = len(num_list)-1 #最多進行（列表長度-1）輪遍歷就可以完成排序
for epoch in range(epochs):
exchanged = False
for i in range(len(num_list)-1-epoch): #每一輪都要進行(len(num_list)-1-epoch)次比較
if num_list[i]>num_list[i+1]: #前一個元素大于后一個，需要交換
temp = num_list[i]
num_list[i] = num_list[i+1]
num_list[i+1] = temp
exchanged = True #本次遍歷發(fā)生了交換，記錄下來
if False == exchanged: #本次遍歷沒有發(fā)生交換，表明序列已經(jīng)有序
return num_list
def main():
test_list = [54,26,93,17,77,31,44,55,20]
print('冒泡排序：')
print(bubble_sort(test_list))
if __name__ == "__main__":
main()
運行結(jié)果為：
冒泡排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
冒泡排序的時間成本很高，除非是每一次相鄰元素間的比較或交換有特殊的用途，否則不建議使用這種排序方式。
選擇排序
一個選擇排序在他遍歷時尋找最大的值，并在完成遍歷后，將其放置在正確的位置。與冒泡排序一樣，在第一次遍歷后，最大的項在正確的地方。 第二遍后，下一個最大的就位。遍歷 （n-1） 次排序 n 個項，因為最終項必須在第（n-1）次遍歷之后。選擇每次遍歷列表只做一次交換，因而通常情況下要快于冒泡排序。
# 選擇排序
def selection_sort(num_list):
epochs = len(num_list)-1 #進行（列表長度-1）輪遍歷就可以完成排序
for epoch in range(epochs):
max_index = 0
for i in range(len(num_list)-epoch): # 下標(biāo)從0到(len(num_list)-epoch-1)都是最大元素候選位置
if num_list[i] > num_list[max_index]: #發(fā)現(xiàn)更大的元素，記錄其位置
max_index = i
#交換
temp = num_list[max_index]
num_list[max_index] = num_list[-epoch-1]
num_list[-epoch-1] = temp
return num_list
def main():
test_list = [54,26,93,17,77,31,44,55,20]
print('選擇排序：')
print(selection_sort(test_list))
if __name__ == "__main__":
main()
運行結(jié)果為：
選擇排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
選擇排序雖然交換的次數(shù)更少，但選擇排序與冒泡排序有相同數(shù)量的比較，因此也是 O(n^2 )的時間復(fù)雜度。
插入排序
插入排序始終在列表中維護一個排序的子列表。然后將每個新項 “插入” 到這個排序好的子列表，并使得子列表繼續(xù)保持排序狀態(tài)。直到所有元素都被加入子列表則完成排序。
每一次“插入”操作都有O(n)的時間復(fù)雜度?！安迦搿辈僮骺梢跃唧w為子列表中比新元素大的都要后移一位，最終新元素直接放入合適的位置。
# 插入排序
def insertion_sort(num_list):
for inserting_index in range(1, len(num_list)): #從索引1到列表最后一個元素逐個插入
inserting_value = num_list[inserting_index]
i = inserting_index-1 #從前一個元素開始，向前逐個比較
while i>=0 :
if num_list[i]>inserting_value: #比帶插入元素大的元素都需要后移一位
num_list[i+1] = num_list[i]
else: #找到了一個小于等于待插入元素的值，則插入上一個位置，并跳出循環(huán)
num_list[i+1] = inserting_value
break
i -= 1 #向前
num_list[i+1] = inserting_value # 在上一個位置插入
return num_list
def main():
test_list = [54,26,93,17,77,31,44,55,20]
print('插入排序：')
print(insertion_sort(test_list))
if __name__ == "__main__":
main()
運行結(jié)果為：
插入排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
插入排序的時間復(fù)雜度依然為O(n^2)。
希爾排序
希爾排序通過將原始列表分解為多個較小的子列表來改進插入排序。每個子列表使用插入排序進行排序。 這里不是將列表拆分為連續(xù)項的子列表，希爾排序使用增量方式，等距取元素組成子列表。這種拆分方式下，增量大小與子列表的數(shù)目相同。逐漸減小增量直至1，就可以得到排序好的列表。
我們將增量從長度的一半開始，每次都將增量減半，直至1。
# 希爾排序所需要的插入排序
# start_index為子序列的起始位置，increment為增量。
def shell_insertion_sort(num_list, start_index, increment):
for inserting_index in range(start_index+increment, len(num_list), increment): #從索引(start_index+increment)到子列表的最后一個元素逐個插入
inserting_value = num_list[inserting_index]
i = inserting_index-increment #從前一個元素開始，向前逐個比較
while i>=start_index :
if num_list[i]>inserting_value: #比帶插入元素大的元素都需要后移增量位
num_list[i+increment] = num_list[i]
else: #找到了一個小于等于待插入元素的值，則插入上一個位置，并跳出循環(huán)
num_list[i+increment] = inserting_value
break
i -= increment #向前
num_list[i+increment] = inserting_value # 在上一個位置插入
return num_list
# 希爾排序
def shell_sort(num_list):
increment = len(num_list)//2 #增量的初值取列表長度的一半
while increment > 0:
for start_index in range(0,increment): #子列表的起始點
shell_insertion_sort(num_list, start_index, increment) #為每個子列表排序
increment = increment//2 #增量減半
return num_list
def main():
test_list = [54,26,93,17,77,31,44,55,20]
print('希爾排序：')
print(shell_sort(test_list))
if __name__ == "__main__":
main()
運行結(jié)果為：
希爾排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
希爾排序的時間復(fù)雜度很難計算，根據(jù)增量衰減的方式不同而不同，但整體傾向于落在 O(n) 和 O(n^2 ) 之間的某處。
