排序是编程中最为常见的操作之一，也是极为基础的算法。本节将快速回顾几种经典的排序方式，并用python实现它们。
为了简单起见，我们只进行数字的排序，且统一为从小到大排序。（在实际的python使用中，可以直接用list.sort()函数完成排序。）
冒泡排序
冒泡排序需要多次遍历列表。它比较相邻的项并交换那些无序的项。每次遍历列表将下一个最大的值放在其正确的位置。
# 冒泡排序
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 #本次遍历发生了交换，记录下来
if False == exchanged: #本次遍历没有发生交换，表明序列已经有序
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()
运行结果为：
冒泡排序：
[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): # 下标从0到(len(num_list)-epoch-1)都是最大元素候选位置
if num_list[i] > num_list[max_index]: #发现更大的元素，记录其位置
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()
运行结果为：
选择排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
选择排序虽然交换的次数更少，但选择排序与冒泡排序有相同数量的比较，因此也是 O(n^2 )的时间复杂度。
插入排序
插入排序始终在列表中维护一个排序的子列表。然后将每个新项 “插入” 到这个排序好的子列表，并使得子列表继续保持排序状态。直到所有元素都被加入子列表则完成排序。
每一次“插入”操作都有O(n)的时间复杂度。“插入”操作可以具体为子列表中比新元素大的都要后移一位，最终新元素直接放入合适的位置。
# 插入排序
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: #找到了一个小于等于待插入元素的值，则插入上一个位置，并跳出循环
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()
运行结果为：
插入排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
插入排序的时间复杂度依然为O(n^2)。
希尔排序
希尔排序通过将原始列表分解为多个较小的子列表来改进插入排序。每个子列表使用插入排序进行排序。 这里不是将列表拆分为连续项的子列表，希尔排序使用增量方式，等距取元素组成子列表。这种拆分方式下，增量大小与子列表的数目相同。逐渐减小增量直至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: #找到了一个小于等于待插入元素的值，则插入上一个位置，并跳出循环
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()
运行结果为：
希尔排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
希尔排序的时间复杂度很难计算，根据增量衰减的方式不同而不同，但整体倾向于落在 O(n) 和 O(n^2 ) 之间的某处。
