二路归并排序算法
原创
二路归并排序算法简单理解就是两两进行比较，然后把他们合并到一起。 通俗理解就是去买衣服的时候，经常会货比三家，看了一个店选两件衣服，然后又去另外一个店选了同款的两件衣服。看价格排序，或者性价比排序 一下，看哪个更便宜，或者性价比更高。
二路归并排序关键点：
- 相邻的两两进行比较，然后把他们合并在一起。相邻的两两最开始是单个元素，合并之后就会翻倍。
- 二路归并排序的过程，需要先拆分元素，然后再合并。
二路归并排序是不稳定的排序，时间复杂度o(n^2), 空间复杂度o(n)
举一个例子看一下二路归并排序的过程：
以数组 5,3,2,1 为例子
- 先拆分数组， 分成两组，5,3 和 2,1
- 继续拆分，两组变成四组， 5,3,2,1各自都是一组
- 两两进行合并，合并成两组， 3,5和1,2
- 再两两合并，合并成一组， 1,2,3,5
二路归并排序算法
看一下用python是如何实现的
def merge_list(elements, low, mid, high):
tmp = [0] * (high - low + 1)
index = 0
left = low
right = mid + 1
while left <= mid and right <= high:
if elements[left] < elements[right]:
tmp[index] = elements[left]
left = left + 1
else:
tmp[index] = elements[right]
right = right + 1
index = index + 1
while left <= mid:
tmp[index] = elements[left]
left = left + 1
index = index + 1
while right <= high:
tmp[index] = elements[right]
right = right + 1
index = index + 1
for i in range(len(tmp)):
elements[low + i] = tmp[i]
def merge_sort(elements, low, high):
if low < high:
mid = int((low + high) / 2)
merge_sort(elements, low, mid)
merge_sort(elements, mid + 1, high)
merge_list(elements, low, mid, high)
if __name__ == '__main__':
arr = [5, 2, 3, 1]
merge_sort(arr, 0, len(arr) - 1)
print(arr)运行后输出结果：
[1, 2, 3, 5]
更多内容可以关注公众号： IT技术漫漫谈
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
腾讯云开发者
