前几天看了下《编程珠玑》，里面提到归并排序算法，用来做磁盘文件排序的。最近又想写博客的想法，又不知从何处开始，所幸，就从这个算法聊起吧。以输出作为学习的目的，兴许会加深对算法的理解，多少打下些基础，以备不时执行。
1、什么是归并排序？
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；使每个子序列有序，在使子序列合并。
2、时间复杂度和空间复杂度是什么？
O(n*Logn) O(n)
3、用python语言如何实现？
1 #!/usr/bin/env python
2 # -*- coding:utf-8 -*-
3 def merge_sort(nums):
4 if len(nums) <= 1
:
5 return nums
6 n =
len(nums)
7 mid = n/2
8 res1 =
merge_sort(nums[:mid])
9 res2 =
merge_sort(nums[mid:])
10 res =
merge(res1, res2)
11 return res
12
13 def merge(res1, res2):
14 i =
0
15 j =
0
16 res =
[]
17 while i < len(res1)
and j <
len(res2):
18 if res1[i] <
res2[j]:
19 res.append(res1[i])
20 i += 1
21 else:
22 res.append(res2[j])
23 j += 1
24 res +=
res1[i:]
25 res +=
res2[j:]
26 return res
27
28 a = [1,7,5,8,3,6,2,0,19
]
29 res = merge_sort(a)
转载于:https://www.cnblogs.com/nixiaocang/p/6481769.html
相关资源：归并排序 C语言实现
