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 🙆
