接上一篇，这节将回顾两种效率较高的排序方法——归并排序和快速排序。
归并排序
归并排序（图片来自百度百科）
归并排序的思想如图所示。先对整个列表做分解，逐步分解为不需要排序的最短列表（包含1个或0个元素）；再将这些元素逐步合并出越来越长的有序列表。
归并排序体现了分而治之的思想。
实现代码如下：
# 归并排序
def merge_sort(num_list):
if len(num_list) < 2: #长度小于2的列表不需要排序
return num_list
#从中间拆分为两个子列表
mid_index = len(num_list)//2
left_list = num_list[:mid_index]
right_list = num_list[mid_index:]
#对两个子列表排序
left_list = merge_sort(left_list)
right_list = merge_sort(right_list)
#将两个排序好的列表合并
left_index = 0 #左侧子列表的索引
right_index = 0 #右侧子列表的索引
all_index = 0 #num_list列表的索引
while left_index<len(left_list) and right_index<len(right_list): #两子列表都未遍历完
if left_list[left_index]<right_list[right_index]: #左侧列表的当前元素更小
num_list[all_index] = left_list[left_index] #将左侧列表的当前元素放入总列表
left_index += 1 #左侧列表索引右移一位
else: # 右侧列表的当前元素更小，或一样大
num_list[all_index] = right_list[right_index] #将右侧列表的当前元素放入总列表
right_index += 1 #右侧列表索引右移一位
all_index += 1 #总列表索引右移一位
while left_index<len(left_list): #左侧子列表未遍历完
num_list[all_index] = left_list[left_index] #将左侧列表的当前元素放入总列表
left_index += 1 #左侧列表索引右移一位
all_index += 1 #总列表索引右移一位
while right_index<len(right_list): #右侧子列表未遍历完
num_list[all_index] = right_list[right_index] #将右侧列表的当前元素放入总列表
right_index += 1 #右侧列表索引右移一位
all_index += 1 #总列表索引右移一位
return num_list
运行结果为：
归并排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
归并排序的拆分操作，时间复杂度为O(logn)；合并操作，时间复杂度为O(n)。因而总的时间复杂度为O(nlogn)。
快速排序
快速排序（图片来自百度百科）
快速排序首先选择一个值，该值称为基准数。基准数通常使用列表中的第一项。基准数的作用是帮助拆分列表。基准数在一轮遍历后将直接放到最终的位置。
左标记从左侧开始遍历列表，直到我们找到一个大于基准数的项。
右标记从右侧开始遍历列表，直到我们找到一个小于基准数的项。
交换这两个项，随后左右标记继续遍历列表。不断重复这个过程。直到在右标记变得小于左标记的时刻，我们停止。
此时，右标记所在的项一定小于基准值，因为这是左标记走过的位置；左标记所在的项一定大于基准值，因为这是右标记走过的项。
右标记所在的项与列表第一项即基准数相交换。此时原数列就别分成了左侧都小于基准数，右侧都大于基准数的两个子序列。进而可以继续对这两个子序列排序。
实现代码如下：
# 快速排序
def quick_sort(num_list):
if len(num_list) < 2: #长度小于2的列表不需要排序
return num_list
base_value = num_list[0] #取得列表第一项为基准数
left_index = 1 #左标记
right_index = len(num_list)-1 #右标记
while True:
# 向右移动左标记直到超过右标记或找到大于基准数的项
while left_index <= right_index:
if num_list[left_index] <= base_value:
left_index += 1
else:
break
# 向左移动右标记直到超过左标记或找到小于基准数的项
while left_index <= right_index:
if num_list[right_index] >= base_value:
right_index -= 1
else:
break
# 当左标记所在位置不大于右标记，交换这两项
if left_index<=right_index:
temp = num_list[left_index]
num_list[left_index] = num_list[right_index]
num_list[right_index] = temp
left_index += 1
right_index -= 1
else: #否则，左侧标记所在位置已经大于右标记，停止。
break
#交换右标记所在项与列表第一项
num_list[0] = num_list[right_index]
num_list[right_index] = base_value
#分而治之
left_list = num_list[:right_index]
right_list = num_list[right_index+1:]
return quick_sort(left_list)+[num_list[right_index]]+quick_sort(right_list)
def main():
test_list = [54,26,93,17,77,31,44,55,20]
print('快速排序：')
print(quick_sort(test_list))
if __name__ == "__main__":
main()
运行结果为：
快速排序：
[17, 20, 26, 31, 44, 54, 55, 77, 93]
快速排序的时间复杂度在O(nlogn)与O(n^2)之间。
事实上，本文所写的代码并不能达到归并排序和快速排序理论能达到的时间复杂度。因为在代码中使用了切片运算符和列表连接运算符。
如果当我们进行递归调用时，简单地传递开始和结束索引与列表本身。那么我们就可以在时间复杂度上达到最佳，空间复杂度也会减少。你可以自己尝试写出这样的代码。
def merge_sort(num_list, start , end):
pass
def quick_sort(num_list, start , end):
pass
