排序算法（二） 谢尔排序

排序算法（二） 谢尔排序

本文为学习数据结构与算法Python版的个人笔记

谢尔排序

谢尔排序就是多个子列表的插入排序，
时间复杂度介于 O ( n ) O(n) O(n)与 O ( n 2 ) O(n^2) O(n2)之间

def shellSort(alist):gap=len(alist)while gap>=1:gap=gap//2for i in range(gap):alist=sub_insertSort(alist,i,gap)return alistdef sub_insertSort(alist,startp,gap):for i in range(startp,len(alist),gap):currentvalue=alist[i]position=iwhile position>=gap and alist[position-gap]>currentvalue:alist[position]=alist[position-gap]position=position-gapalist[position]=currentvaluereturn alist

归并排序

思想就是二分法，然后分别排序，然后在一起排序
时间复杂度 O ( n l o g n ) O(nlog_n) O(nlogn​)
算法运行过程中需要额外存储空间

def mergeSort(alist):if len(alist)<=1:return alistmid=len(alist)//2lefthalf=alist[:mid]righthalf=alist[mid:]lefthalf=mergeSort(lefthalf)righthalf=mergeSort(righthalf)merge=[]t=0i=0j=0while i<len(lefthalf) and j <len(righthalf):if lefthalf[i]<righthalf[j]:merge.append(lefthalf[i])i=i+1else:merge.append(righthalf[j])j=j+1t=t+1if len(lefthalf[i:])>0:merge=merge+lefthalf[i:]else:merge=merge+righthalf[j:]return merge# print(mergeSort(alist))

快速排序

时间复杂度 O ( n l o g n ) O(nlog_n) O(nlogn​)
思想就是确定一个中值，把数据分成两半，一半比中值小的，一半比中值大的，然后继续继续递归一直到当前数据里只有一个数字。
算法运行过程中不需要额外存储空间

def partsplit(alist,first,last):midvalue=alist[first]left=firstright=lastwhile left<right:while alist[left]<=midvalue and left<last:left=left+1while alist[right]>=midvalue and right>first:right=right-1if left<right:alist[left],alist[right]=alist[right],alist[left]alist[first],alist[right]=alist[right],alist[first]return rightdef fastSort(alist,first,last):if first<last:splitpoint=partsplit(alist,first,last)fastSort(alist,first,splitpoint-1)fastSort(alist,splitpoint+1,last)

或者

def fastSort(alist):if len(alist)<2:return alistfirst=0last=len(alist)-1midvalue=alist[first]left=firstright=lastwhile left<right:while alist[left]<=midvalue and left<last:left=left+1while alist[right]>=midvalue and right>first:right=right-1if left<right:alist[left],alist[right]=alist[right],alist[left]alist[first],alist[right]=alist[right],alist[first]lefthalf=fastSort(alist[:right])righthalf=fastSort(alist[right+1:])return lefthalf+[alist[right]]+righthalfprint(fastSort(alist))

自己实现的时候遇到的一个坑是

 lefthalf=fastSort(alist[:right])righthalf=fastSort(alist[right+1:])return lefthalf+[alist[right]]+righthalf

这一段，我直接下面这样，不return直接在原alist上也是一个意思，就是没有单独保留中值

lefthalf=fastSort(alist[:right])
righthalf=fastSort(alist[right:])
return lefthalf+righthalf

这样会出现死循环，比如[17,26,20]，会一直递归出一个[]和[17,26,20]