最近准备去找工作，时隔几年又要把在学校时代压床底的算法掏出来吹吹灰尘了，真有种朝花夕拾的感觉…哈哈哈哈
毕竟如果面试要是写不出来，那真是太尴尬了。
写那么一波插归并序找找感觉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)，不过由于归并排序需要额外的空间，所以也是一种拿空间换时间的策略。