012归并排序.md

归并排序

什么是归并排序

归并排序是诸多排序算法中的一种，主要特点是能用于外部排序，也就是说如果内存不能承载全部排序数据时，可以用归并排序来实现。为了简单我们主要介绍二路归并。

如何实现归并排序

首先还是准备测试的数组，然后用递归来调用merge_sort函数。

def merge_sort(a):
  # a is the array

  if len(a) <= 1:
    return a

  middle = len(a) / 2
  left_array = merge_sort(a[0:middle])
  right_array = merge_sort(a[middle:])
  return merge(left_array, right_array)

def merge(left_array, right_array):
  # left_array is the array
  # right_array is the array
  pass

a = [3, 2, 2, 1, 5, 4]
merge_sort(a)

然后最重要的是merge函数，也就是如何合并两个已经排序的数组，这也是外部排序需要解决的。

def merge(left_array, right_array):
  # left_array is the array
  # right_array is the array

  result = []
  left = 0
  right = 0

  while left < len(left_array) and right < len(ri\
ght_array):
    if left_array[left] <= right_array[right]:
      result.append(left_array[left])
      left += 1
    else:
      result.append(right_array[right])
      right += 1

  result += left_array[left:]
  result += right_array[right:]
  return result

a = [3, 2, 2, 1, 5, 4]
print(merge_sort(a))
# Print [1, 2, 2, 3, 4, 5]

这是本章内容，希望对你有所帮助。进入下一章