# -*- coding: utf-8 -*-
def merge(array, start, middle, end):
n1 = middle - start + 1 # 第一个子序列长度
n2 = end - middle # 第二个子序列长度
left_array = []
right_array = []
for i in range(n1):
left_array.append(array[start + i])
for i in range(n2):
right_array.append(array[middle + i + 1])
left_array.append(float('Inf')) # float('Inf') 表示正无穷
right_array.append(float('Inf'))
i = j = 0
for index in range(start, end + 1):
if (left_array[i] <= right_array[j]):
array[index] = left_array[i]
i += 1
else:
array[index] = right_array[j]
j += 1
return array
def merge_sort(array, start, end):
if start < end:
middle = (start + end) // 2
merge_sort(array, start, middle)
merge_sort(array, middle + 1, end)
merge(array, start, middle, end)
array = [1, 9, 2, 6, 7, 8, 8, 7, 9, 11, 18, 12, 13]
merge_sort(array, 0, len(array) - 1)
print(array)
归并排序
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
- 一般来说，这三者的时间复杂度O(NlogN)，空间复杂度O(n)优化后，空间复杂度均可为O(1)，如下文中的快排和...
- 转载：http://blog.csdn.net/pzhtpf/article/details/7559943 一、...
