手摇算法实现原地归并排序 python

1：手摇算法（内存翻转）

第一次见到这个是在做字符串转换的时候见到的，不知道是手摇算法；
问题是这样：

给定字符串 dog loves pig
变为 pig loves dog

解决方法
先将每个单词进行翻转，然后整个翻转可以达到效果

2：原地归并

两个有序数组进行合并，空间复杂度为O(1)
用两个指针分别指向两个数组的起始

IMG_7077.JPG

3：归并排序

就是正常的归并排序

4：代码如下

def handreverse(a,i,index,j):
    c =[]
    c1 = []
    c2 = []
    c3 = []
    if i == 0:
        for each in a[index-1::-1]:
            c1.append(each)
    else:
        for each in a[index-1:i-1:-1]:
            c1.append(each)
    for each in a[j-1:index-1:-1]:
        c2.append(each)
    c3 = c1 + c2
    c3.reverse()
    c = a[0:i] + c3 + a[j:]
    for i in range(0,len(a)):
        a[i] = c[i]
    return a
def merge(a,lo,hi):
    mid = (lo + hi) / 2
    i = lo
    j = mid +1
    while i<j and j<=hi:
        while i<j and a[i]<=a[j]:
            i += 1
        index = j
        while j<=hi and a[j]<a[i]:
            j += 1
        handreverse(a,i,index,j)
        i = i + (j - index)
    return a
def sort(a,lo,hi):
    if lo < hi:
        mid = (lo + hi) /2
        sort(a,lo,mid)
        sort(a,mid+1,hi)
        merge(a,lo,hi)
    return a 

handreverse() 函数写的太难看了·····

5：遇到的坑

1：handreverse里面加了一个判断，这个是当list为[1]如果取a[1:-1:-1]取不到
2：改为a[index-1:-1]会取到全部的，大概是我比较蠢，第三遍才取到
3：以前用c复制数组的时候直接c = a,c[1] = a[1],python 用list.append(num)
4：注意要改变lista的值，不然又不能排序
5：merge函数中i是要往后推，我觉得没必要啊，反正也要找到比a[j]大的。不理解
6：merge函数中的a[i] <= a[j]不然的话若遇到数组中又相同的元素就无法跳出循环

归并排序中的这个归并过程还可以用来找逆序对和计算Kendall tau 距离 明天实现一下。
最后
效率太低了，写个这写了一下午，乱七八糟的错误一直在修改 TAT 🙆