【算法作业记录】

插入排序 递归实现

直接插入

#将a[n]插入有序区间a[0,n-1]中 时间复杂度 O（n）
def Insert(a,n):i=nwhile(i>0 and a[i-1]>a[i]):tmp=a[i]a[i]=a[i-1]a[i-1]=tmpi-=1return
#直接插入排序
def Insertsort(a,n):for i in range(1,n):#【1，n-1】if(a[i-1]>a[i]):Insert(a,i)return      
#递归法实现直接插入：插入a[n]是建立在a[0,n-1]有序的基础之上
def RecursionInsertsort(a,n):if(n<=0):returnRecursionInsertsort(a,n-1)#递归实现【0，n-1】有序if(a[n-1]>a[n]):Insert(a,n)#再把a[n]插入有序数组a[0,n-1]中return

折半插入

#折半查找#在有序区[0,i-1]中二分查找元素a[i]应插入的位置 时间复杂度O（logN）
def BinInsert(a,i):low=0height=i-1insert=a[i]while(low<=height):mid=(low+height)//2if(insert<a[mid]):height=mid-1else:    low=mid+1    j=i-1#height+1为要插入的位置，将【height+1,i-1】元素往后平移一步，空出a[height+1]的位置   while(j>=height+1):a[j+1]=a[j]j=j-1a[height+1]=insert      #折半插入排序
def BinInsertSort(a,n):for i in range(1,n):if(a[i-1]>a[i]):BinInsert(a,i)print(str(i)+":"+str(a))
#递归实现折半插入
def RecursionBinInsertSort(a,n):if(n<=0):returnRecursionBinInsertSort(a,n-1)if(a[n-1]>a[n]):BinInsert(a,n)return    list1 = [1,4,6,3,7,9,2,8,5,0]        
print("排序前："+str(list1))
#Insertsort(list1,len(list1))    
#RecursionInsertsort(list1,len(list1)-1)    
#BinInsertSort(list1,len(list1))
RecursionBinInsertSort(list1,len(list1)-1)
print("排序后："+str(list1))

归并排序的算法改进

还有一个链表自底向上的未实现，参考笔记点我 点我

#107552304105 吕雅轩
#由于本人能力有限 除了网上给的四个优化策略想不出其它的了，以下是实现过程
#策略1: 若两数组直接拼起来就是有序的，就无需merge 即当arr[mid]<=arr[mid+1]
#策略2：小区间使用性能更高的插入排序
#策略3：全程使用1个和待排数组大小一样的临时数组作为辅助空间，避免了每一次merge都要new的浪费
#策略4：自顶向下需要递归调用log(n)的函数栈空间，可用自底向上的思路优化
#策略5：归并算法的空间复杂度是O(n),若想使空间复杂度优化为O（1）,可以采用自底向上的链表法进行排序。
def merge_sort(a):#策略3：全局辅助空间global alal=list(range(len(a)))#_mergeSort(a,0,len(a)-1)#策略4：迭代法自底向上_mergeSortIterate(a)return#插入排序
def _insertSort(a,l,r):for i in range(l,r+1):#【1，n-1】if(a[i-1]>a[i]):j=iwhile(j>0 and a[j-1]>a[j]):tmp=a[j]a[j]=a[j-1]a[j-1]=tmpj-=1#用辅助空间把两个有序数组合并
def _merge_two_sorted_array(a,l,mid,r):for i in range(l,r+1):#[l,r]al[i]=a[i]i=l#左半有序数组的起始下标j=mid+1#右半有序数组的起始下标  #print(str(l)+":"+str(mid)+":"+str(r)+":"+str(a))  for k in range(l,r+1):#[l,r]if i==mid+1:a[k]=al[j]j+=1elif j>r:a[k]=al[i]i+=1elif al[i]<al[j]:a[k]=al[i]i+=1else:assert al[i]>=al[j]a[k]=al[j]j+=1 return
#递归实现归并排序
def _mergeSort(a,l,r):if l>=r:return#策略2：小区间使用性能更高的插入排序if (r-l)<=7:_insertSort(a,l,r)returnmid=l+(r-l)//2#防止(l+r)溢出_mergeSort(a,l,mid)_mergeSort(a,mid+1,r)#策略1：若有序左区间的最大元素小于有序右区间的最小元素，可直接合并if a[mid]<=a[mid+1]:return_merge_two_sorted_array(a,l,mid,r)return#策略4：迭代法自底向上
def _mergeSortIterate(a):n=len(a)size=1#每一次分段的长度i=0while(size<=n):i=0while(i+size<n):#确保后一段的存在，同时保证不越界_merge_two_sorted_array(a,i,i+size-1,min(i+size+size-1,n-1))i+=size+sizesize+=sizereturnlist1 = [10,9,8,7,6,4,5,3,2,1]        
print("排序前："+str(list1))
merge_sort(list1)
#_mergeSortIterate(list1)
print("排序后："+str(list1))