python培训之归并排序的实现原理

　　python归并排序的实现原理

　　原理分析

　　1、把一个序列从中间位置分成两个序列;

　　2、把这两个子序列按第一步继续分成两部分;

　　3、直到所有子序列的长度都是1，也就是说，不能再有二分截止。此时再两两合并成一个有序的序列。

　　实例

　　def merge(arr, low, mid, high):

　　# low 和 high 为整个数组的第一个和最后一个位置索引，mid 为中间位置索引

　　# i 和 j 为指针，最初位置分别为两个有序序列的起始位置

　　# ltmp 用来存放合并后的序列

　　i = low

　　j = mid+1

　　ltmp = []

　　while i <= mid and j <= high: # 只要左右两边都有数

　　if arr[i] < arr[j]: # 当左边的数小于右边的数

　　ltmp.append(arr[i]) # 将左边的数存入 ltmp

　　i += 1 # 左边的指针往右移一位

　　else: # 当右边的数小于左边的数

　　ltmp.append(arr[j]) # 将右边的数存入 ltmp

　　j += 1 # 右边的指针往右移一位

　　# 上面的 while 语句执行完后，左边或者右边没有数了

　　while i <= mid: # 当左边还有数的时候

　　ltmp.append(arr[i]) # 将左边剩下的数全部存入 ltmp

　　i += 1

　　while j <= high: # 当右边还有数的时候

　　ltmp.append(arr[j]) # 将右边剩下的数全部存入 ltmp

　　j += 1

　　arr[low:high+1] = ltmp # 将排序后的数组写回原数组

　　def merge_sort(arr, low, high): # low 和 high 为整个数组的第一个和最后一个位置索引

　　if low < high: # 至少有两个元素

　　mid = (low + high) // 2

　　merge_sort(arr, low, mid) # 把左边递归分解

　　merge_sort(arr, mid+1, high) # 把右边递归分解

　　merge(arr, low, mid, high) # 做归并

　　以上就是python归并排序的实现原理，希望对大家有所帮助。更多Python学习指路：请关注多测师。https://www.e70w.com/xwzx/