归并排序
归并排序，又名Merge Sort，是建立在归并操作上的一种有效的排序算法。其具体原理有2个关键字：分与治。
分：我们需要进行分的操作，将数列均衡的分成2部分（n//2），当然如果是奇数，可以自己决定将多余的数分到前半部分，还是后半部分。当分成2部分之后，在递归的对左右子序列继续2分，以此类推，直到只有1个元素，再也分不下去。
治：所有元素分完之后，开始大小比较归并操作，从2个元素开始进行归并的比较，直到归并到n//2为止。
其时间复杂度为：O(n log n) 。
图解归并排序
相信读者看完原理就应该直到了，治其实就是分的反操作。当然，原理毕竟还是可能不容易理解，下面博主用图给大家绘制出归并排序的步骤：
图解应该很好看懂，就是先分解，在合并，不过合并的过程中唯一与分解过程不同的地方是，需要对其进行排序。
实战：归并排序
这应该是数据结构的最后一个算法，不过算法并不仅仅只有这些。通过这些基础的算法所衍生出来的算法其实也是很多的，所以别小看这些算法。
回到我们今天的主题，下面我们通过Python代码来实现归并排序，示例如下：
def merge(left, right): r, l = 0, 0 temp = [] # 临时列表 lmax = len(left) rmax = len(right) while l < lmax and r < rmax: if left[l] < right[r]: # 排序，小于等于的放左边 temp.append(left[l]) l += 1 else: temp.append(right[r]) # 排序，大的放右边 r += 1 temp += list(left[l:]) temp += list(right[r:]) return temp def merge_sort(my_list): if len(my_list) <= 1: # 当数列长度小于1时，直接返回 return my_list mid = len(my_list) // 2 # 获取对半索引为止 left = merge_sort(my_list[:mid]) # 递归方法归并左边列表 right = merge_sort(my_list[mid:]) # 递归方法归并右边列表 return merge(left, right) # 并归返回结果 if __name__ == "__main__": my_list = [8, 0, 4, 3, 2, 1] print("排序前的数组：", my_list) print("排序后的数组：", merge_sort(my_list))
运行之后，效果如下：
