最近准备去找工作,时隔几年又要把在学校时代压床底的算法掏出来吹吹灰尘了,真有种朝花夕拾的感觉…哈哈哈哈
毕竟如果面试要是写不出来,那真是太尴尬了。
写那么一波插归并序找找感觉2333

运行环境 Runtime environment

1
2
3
操作系统: Windos10  
IDE: JetBrains Python 2018.2.4 x64
语言: Python 3.66

背景

比较高端的一种排序方式,在做排序的时候是个不错的选择。
在我看来,归并和快速两种排序,在实际开发用到了,都是挺有逼格的。

归并排序

在归并排序的时候,将数组不断的拆分为两半,直到数据只剩一个的时候,然后再按照大小顺序将拆分的数据组合起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
temp = []
left_p, right_p = 0, 0
while left_p < len(left) and right_p < len(right):
if left[left_p] < right[right_p]:
temp.append(left[left_p])
left_p += 1
else:
temp.append(right[right_p])
right_p += 1
temp += (left[left_p:])
temp += (right[right_p:])
return temp
def main():
numbers = [6, 3, 10, 5, 45, 9, 2, 7, 23, 4, 14]
numbers = merge_sort(numbers)
print(numbers)

拆成多个函数来实现,方便理解。

总结

  1. 对于分别有序的两个数组,通过每次取出一个数据比较,将较小的那个放到新的数组中,较大的那个等待下次继续比较,就这样一直取,比较,取,比较,直到两个数组的数都放在了新的数组中。返回新的数组。
  2. 大体的流程还是通过递归实现的,其实大部分分治的算法都是通过递归搞定的,方便理解。
  3. 就效率而言,归并排序是六种排序中时间复杂度最好的,即使是最差情况,都是O(nlogn),不过由于归并排序需要额外的空间,所以也是一种拿空间换时间的策略。