[数据结构与算法][每日一水] 归并排序 Python实现

(建议先看后边的伪代码分析，然后自己写出来)

先上代码：

import numpy as np


length = 100000
array = np.arange(0, length)
np.random.shuffle(array)


def merge(array, s1, e1, s2, e2):
    array_new = array.copy()
    # 规定从小到大
    
    steps = (e1-s1+1) + (e2-s2+1)
    start = s1
    for i in range(steps):
        
        if s1 > e1:
            array_new[start+i] = array[s2]
            s2 += 1
            continue
            
        if s2 > e2:
            array_new[start+i] = array[s1]
            s1 += 1
            continue
        
        if   array[s1] >= array[s2]:
            array_new[start+i] = array[s2]
            s2 += 1
            
        elif array[s1]  < array[s2]:
            array_new[start+i] = array[s1]
            s1 += 1
    
    array[start:e2+1] = array_new[start:e2+1]
    
    return array_new
        


def mergeSort(array, start, end):
    # 规定从小到大
    
    if end-start == 1:
    	
        if array[start] > array[end]:
            array[start] += array[end]
            array[end] = array[start] - array[end]
            array[start] = array[start] - array[end]
        return array
    
    if end == start:
        return array
    
    mid   = int((start + end) / 2)
    
    mergeSort(array, start, mid)
    mergeSort(array, mid+1, end)
    
    merge(array, start, mid, mid+1, end)

print(array)    
mergeSort(array, 0, length-1)
print(array)

俺是非科班出生的菜鸡，一大把年纪了，第一次写归并排序😭😭😭😭

不过好在写出来了，算法复杂度是 $O(nlog(n))$，上课老师说，插入排序的是线性下降的，而归并排序是指数下降的，所以更快，感觉是听懂了

简单说下这个 mergeSort 的想法：

def mergeSort():
	
	% 先处理最简单的情况
	% 例如数组长度只有1或者2

	% 然后递归调用 mergeSort 先处理前一半
	% 递归调用 mergeSort 处理后一半

	% 之后 merge 函数将两部分合并起来

就是不断的递归吧，一直递归到最简单的 case

然后 merge 这里有个新手可能有的坑，就是 要用 三个指针 去合并，就是merge函数里的：
start，s1, s2

卜老师的课程里叫这个为 Divide and Conquer

从最简单的 case 开始，然后逐步问题逐步边复杂，给我的感觉就像是数学归纳法

B站也有卜老师的课
https://www.bilibili.com/video/BV1MK4y1W7Gm

老师讲的很nice, 让我这菜鸟也学会了，hxdm，冲