def merge(array, start, mid, end):
""" 归并排序子程序
"""
# 数组切片
len_left = mid - start + 1
len_right = end - mid
# 新建缓存数组
left_arr = []
right_arr = []
for _ in range(len_left):
left_arr.append(array[start + _])
for _ in range(len_right):
right_arr.append(array[mid + _ + 1])
# 设置哨兵
flag = 1 << 24
left_arr.append(flag)
right_arr.append(flag)
i = j = 0
# 将原数组中的元素分别进行大小排序替换
for _ in range(start, end + 1):
if left_arr[i] <= right_arr[j]:
array[_] = left_arr[i]
i += 1
else:
array[_] = right_arr[j]
j += 1
def merge_repeat(array, start, end):
""" 将数组不断的进行拆分
最终将数组化为单个元素，再逐渐进行相邻数组的合并排序
过程模拟：
[5, 2, 4, 7, 1, 3, 2, 6]
[5, 2, 4, 7] [1, 3, 2, 6]
[5, 2] [4, 7] [1, 3] [2, 6]
[5] [2] [4] [7] [1] [3] [2] [6]
[2, 5] [4, 7] [1, 3] [2, 6]
[2, 4, 5, 7] [1, 2, 3, 6]
[1, 2, 2, 3, 4, 5, 6, 7]
"""
if start < end:
mid = (end + start)//2
merge_repeat(array, start, mid)
merge_repeat(array, mid + 1, end)
merge(array, start, mid, end)
def merge_sort(array):
start = 0
end = len(array) - 1
merge_repeat(array, start, end)
if __name__ == '__main__':
arr = [5, 2, 4, 7, 1, 3, 2, 6, 9, 8, 10, 19, 13, 14, 11, 9]
merge_sort(arr)
print(arr) # 输出 [1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 13, 14, 19]
归并排序算法
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 归并排序是是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。 算法思想 把 n 个元...
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
- 一般来说，这三者的时间复杂度O(NlogN)，空间复杂度O(n)优化后，空间复杂度均可为O(1)，如下文中的快排和...
