数据结构第11章 排序

第11章排序11.2插入排序definsertionSort(arr):foriinrange(1,len(arr)):key=arr[i]j=i-1whilej>=0andkey<arr[j]:arr[j+1]=arr[j]j-=1arr[j+1]=keyarr=[59,12,77,64,72,69,46,89,31,9]print('before:',arr)insertionSort(arr)print("after:")foriinrange(len(arr)):print("%d"%arr[i],end='')11.3折半插入排序defbinary_sort(a):foriinrange(0,len(a)):index=a[i]low=0hight=i-1whilelow<=hight:mid=(low+hight)//2ifindex>a[mid]:low=mid+1else:hight=mid-1forjinrange(i,low,-1):a[j]=a[j-1]a[low]=indexli=[511,12,77,64,72,611,46,811,31,11]print('before:',li)binary_sort(li)print('after:',li)11.4希尔排序defshell_sort(alist):n=len(alist)gap=n//2whilegap>0:foriinrange(gap,n):j=iwhilej>=gapandalist[j-gap]>alist[j]:alist[j-gap],alist[j]=alist[j],alist[j-gap]j-=gapgap=gap//2li=[10,11,84,32,112,26,58,111,35,27,46,28,75,211,37,12]print('before:',li)shell_sort(li)print('after:',li)11.5冒泡排序defbubble_sort(alist):forjinrange(len(alist)-1,0,-1):#外循环foriinrange(j):#内循环ifalist[i]>alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]li=[54,26,93,17,77,31,44,55,20]print('before:',li)bubble_sort(li)print('after:',li)11.6快速排序defquick_sort(alist,start,end):ifstart>=end:returnmid=alist[start]low=starthigh=endwhilelow<high:whilelow<highandalist[high]>=mid:high-=1alist[low]=alist[high]whilelow<highandalist[low]<mid:low+=1alist[high]=alist[low]alist[low]=midquick_sort(alist,start,low-1)quick_sort(alist,low+1,end)li=[48,36,61,99,81,14,30]print('before:',li)quick_sort(li,0,len(li)-1)print('after:',li)11.7选择排序defselection_sort(alist):n=len(alist)foriinrange(0,n):min=i#将当前下标定义为最小值下标forjinrange(i+1,n):ifalist[j]<alist[min]:#如果有小于当前最小值的关键字min=j#将此关键字的下标赋值给min_indexifi!=min:#i不是最小数时，将i和最小数交换alist[i],alist[min]=alist[min],alist[i]li=[5,2,1,8,3,4,6,7]print('before:',li)selection_sort(li)print('after:',li)11.8堆排序defbuildMaxHeap(arr):importmathforiinrange(math.floor(len(arr)/2),-1,-1):heapify(arr,i)defheapify(arr,i):left=2*i+1right=2*i+2largest=iifleft<arrLenandarr[left]>arr[largest]:largest=leftifright<arrLenandarr[right]>arr[largest]:largest=rightiflargest!=i:swap(arr,i,largest)heapify(arr,largest)defswap(arr,i,j):arr[i],arr[j]=arr[j],arr[i]defheapSort(arr):globalarrLenarrLen=len(arr)buildMaxHeap(arr)foriinrange(len(arr)-1,0,-1):swap(arr,0,i)arrLen-=1heapify(arr,0)returnarrL=[11,35,25,87,46,31,52,97]print(heapSort(L))10.9.2deque实现堆排序【例11-10】deque实现堆排序举例fromcollectionsimportdequedefswap_param(L,i,j):#把堆顶元素和堆末尾的元素交换L[i],L[j]=L[j],L[i]returnLdefheap_adjust(L,start,end):#heap_adjust函数用于调整为大根堆temp=L[start]i=startj=2*iwhilej<=end:#代表在调整完整棵树树之前一直进行循环if(j<end)and(L[j]<L[j+1]):#保证j取到较大子树的坐标j+=1iftemp<L[j]:#如果子树的根节点小于子树的值,就把根节点和较大的子树的值进行交换L[i]=L[j]i=jj=2*ielse:breakL[i]=tempdefheap_sort(L):#heap_sort函数用于构造大根堆L_length=len(L)-1#引入一个辅助空间first_sort_count=L_length//2foriinrange(first_sort_count):#把序列调整为一个大根堆heap_adjust(L,first_sort_count-i,L_length)foriinrange(L_length-1):L=swap_param(L,1,L_length-i)#把堆顶元素和堆末尾的元素交换（引入的一个辅助空间，序列长度减1）heap_adjust(L,1,L_length-i-1)#把剩下的元素调整为一个大根堆return[L[i]foriinrange(1,len(L))]defmain():L=deque([50,16,30,10,60,90,2,80,70])L.appendleft(0)print(heap_sort(L))if__name__=='__main__':main()10.9.3heapq实现堆排序importheapqdefheapsort(iterable):h=[]forvalueiniterable:heapq.heappush(h,value)return[heapq.heappop(h)foriinrange(len(h))]if__name__=='__main__':li=[50,16,30,10,60,90,2,80,70]print("before:",li)h=heapsort(li)print("after:",h)11.10归并排序defmerge(left,right):i,j=0,0result=[]whilei<len(left)andj<len(right):ifleft[i]<right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresultdefmerge_sort(alist):iflen(alist)<=1:returnalistmid=len(alist)//2left=merge_sort(alist[:mid])right=merge_sort(alist[mid:])returnmerge(left,right)defmain():li=[9,4,6,2,1,7]print("befroe:",li)print("after:",merge_sort(li))if__name__=='__main__':main()11.12.1有序序列插入元素lis=[1,2,7,8,411]print("before:",lis)n=int(input('insertanumber:'))lis.append(n)foriinrange(len(lis)-1):iflis[i]>=n:forjinrange(i,len(lis)):lis[j],lis[-1]=lis[-1],lis[j]breakprint("after:",lis)11.12.2求解第二大整数defbubble_sort(alist):#冒泡排序法forjinrange(len(alist)-1,0,-1):#外循环foriinrange(j):#内循环ifalist[i]<alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]li=[]num=eval(input('请输入整数，必须既有正数，也有负数，以零为结束'))whilenum!=0:li.append(num)num=int(input('请输入整数:'))prin