遍历的方法
尝试用python写最简单的insert sort。但由于对python不熟悉，一开始的时候完全用了c语言的思考方式....
#insert sort
def sort(L):
"""
L : list to be sorted
return : new list from big to small
"""
for i in range(1,len(L)):
key = L[i]
for j in range(i):
if key >= L[j]:
temp1 = L[j]
for k in range(j+1,i+1):
temp2 = L[k]
L[k] = temp1
temp1 = temp2
L[j] = key
break
L = [1,5,6,3,7,8]
sort(L)
print(L)
结果正确，但是写的很复杂。要注意python中本来就有了list这种数据结构，因此可以直接用list的特性。
#insert sort
def sort(L):
"""
L : list to be sorted
return : new list from big to small
"""
for i in range(1,len(L)):
for j in range(i):
if L[i] >= L[j]:
key = L.pop(i)
L.insert(j,key)
break
L = [1,5,6,3,7,8]
sort(L)
print(L)
时间复杂度
我们在计算复杂度的时候，一般情况下我们都假设每个operation都有相同的cost。这样，我们可以说上面的算法有theta(n^2)的时间复杂度。其中，n^2的compare，n^2的swap。而swap的实现方法其实有很多种，如果有一种情况下，compare的耗时要远大于swap，这个时候我们就需要考虑减少compare的时间。其中的一种做法就是用binary search。代码如下所示。
用binary search改进
#insert sort
def binarysearch(L,begin,end,key):
"""
L : list to be search
begin : integer, the begin index when searching
end : integer, the end index when searching
key : integer, value to be compared
return : integer, to be insert
"""
if end == begin:
return begin
elif end - begin == 1:
#print("here")
if key >= begin:
return begin
else:
return end
else:
mid = (begin + end)//2
if key > L[mid]:
end = mid
# print("begin="+str(begin)+" end="+str(end))
return binarysearch(L,begin,end,key)
elif key < L[mid]:
begin = mid
# print(mid)
return binarysearch(L,begin,end,key)
else:
return mid
def sort(L):
"""
L : list to be sorted
return : new list from big to small
"""
for i in range(1,len(L)):
j = binarysearch(L,0,i,L[i])
popnum = L.pop(i)
L.insert(j,popnum)
# print(L)
L = [1,5,6,3,7,8]
sort(L)
print(L)
一开始犯了一个特别愚蠢的错误，在迭代的时候，没有写return。
时间复杂度
nlog(n)的compare，n^2的swap。