Python实现慕课网《数据结构与算法》所有练习题和提高题源代码

Python实现慕课网《数据结构与算法》所有练习题和提高题源代码，并实现了AVL树，拓扑排序，求DAG单源最短路径以及Spfa算法等老师没有给出源码的算法。
项目根目录的repo.py是我设置的代码库，方便import我们已经实现了的代码 我在算法实现过程中的笔记或者思路会以注释的形式标注在代码中

完整版源代码下载地址：
排序算法的实现与性能测试

# -*- coding: utf-8 -*- from random import randint import timeit def bubbleSort(alist): exchange=False for i in range(len(alist)-1,0,-1): for j in range(i): if alist[j]>alist[j+1]: alist[j],alist[j+1]=alist[j+1],alist[j] exchange=True if not exchange: break return alist def selectionSort(alist): for i in range(len(alist)): minposition=i for j in range(i,len(alist)): if alist[minposition]>alist[j]: minposition=j alist[i],alist[minposition]=alist[minposition],alist[i] return alist def insertionSort(alist): for i in range(1,len(alist)): currentvalue=alist[i] position=i while alist[position-1]>currentvalue and position>0: alist[position]=alist[position-1] position=position-1 alist[position]=currentvalue return alist def shellSort(alist): gap=len(alist)//2 while gap>0: for startpos in range(gap): gapInsertionSort(alist,startpos,gap) gap=gap//2 return alist def gapInsertionSort(alist,startpos,gap): #希尔排序的辅助函数 for i in range(startpos+gap,len(alist),gap): position=i currentvalue=alist[i] while position>=gap and alist[position-gap]>currentvalue: alist[position]=alist[position-gap] position=position-gap alist[position]=currentvalue max=5000 list=[randint(-max,max) for x in range(max)] #使用切片可以真正将一份list复制给其他变量，如果不用切片，即alist=list，只是指针而已。 alist=list[:] blist=list[:] clist=list[:] dlist=list[:] ''' 运行次数(number)只能设置成1，因为内存中alist、blist等指向同一个对象，该对象第一次排序后就已经是有序列表了。 所以在这种情况下会发生有趣的现象。按照短路冒泡排序的性质，它在碰到一个有序列表以后会立刻停止遍历，所以不管它的number是1还是10，time都几乎没变化 但其他排序方法，就算对有序列表进行排序，交换是不需要了，但是还要遍历&比较，所以他们的运行次数变多的话，time依旧变大 之前我就是把number设置成100，发现短路冒泡排序简直太快了，才发现这个问题。 ''' t1=timeit.Timer('bubbleSort(alist)','from __main__ import bubbleSort,alist') print('短路冒泡排序: %s s' %t1.timeit(number=1)) t2=timeit.Timer('selectionSort(blist)','from __main__ import selectionSort,blist') print('选择排序: %s s' %t2.timeit(number=1)) t3=timeit.Timer('insertionSort(clist)','from __main__ import insertionSort,clist') print('插入排序: %s s' %t3.timeit(number=1)) t4=timeit.Timer('shellSort(dlist)','from __main__ import shellSort,dlist') print('希尔排序: %s s' %t4.timeit(number=1)) 

二叉堆的实现与堆排序

# -*- coding: utf-8 -*- from repo import mergeSort,quickSort import timeit from random import randint #这里我实施了课程中的heap sort2和heap sort3，分别对应了HeapSort和HeapSortInPlace。第一个算法太简单、算法效率低，直接忽略。 #定义类的时候的参数max，出现在课程4-10中，它限制了堆中元素的个数，可用于以Onlogm的复杂度求n个元素里优先级最大的m个元素。 class MaxHeap(object): def __init__(self,max=100000): self.heapList=[0] self.currentSize=0 self.maximum=max def shiftUp(self,i): currentvalue=self.heapList[i] while i//2>0: if self.heapList[i//2] < currentvalue: self.heapList[i]=self.heapList[i//2] #优化：赋值替代交换 i=i//2 else: break self.heapList[i]=currentvalue def insert(self,k): self.heapList.append(k) self.currentSize+=1 self.shiftUp(self.currentSize) if self.currentSize>self.maximum: #在最大堆中这个操作会保留m个最小的元素。 self.delFirst() def shiftDown(self,i): currentvalue=self.heapList[i] while i*2<=self.currentSize: mc=self.maxChild(i) if currentvalue < self.heapList[mc]: self.heapList[i]=self.heapList[mc] i=mc else: break self.heapList[i]=currentvalue def maxChild(self,i): if i*2+1>self.currentSize: return i*2 else: if self.heapList[i*2]>self.heapList[i*2+1]: return i*2 else: return i*2+1 def delFirst(self): #之所以叫delFirst是因为这个函数可以兼容最大堆和最小堆 retval=self.heapList[1] if self.currentSize==1: self.currentSize-=1 self.heapList.pop() return retval self.heapList[1]=self.heapList[self.currentSize] self.heapList.pop() self.currentSize-=1 self.shiftDown(1) return retval def buildHeap(self,alist): #heapify self.heapList=[0]+alist[:] self.currentSize=len(alist) i=self.currentSize//2 while i>0: self.shiftDown(i) i-=1 overflow=self.currentSize-self.maximum for i in range(overflow): self.delFirst() def HeapSort(self,alist): self.buildHeap(alist) sortedList=[self.delFirst() for x in range(self.currentSize)] sortedList.reverse() return sortedList def HeapSortInPlace(self,alist): self.buildHeap(alist) while self.currentSize>1: self.heapList[1],self.heapList[self.currentSize]=self.heapList[self.currentSize],self.heapList[1] self.currentSize-=1 self.shiftDown(1) return self.heapList[1:] class MinHeap(MaxHeap): #最小堆，继承自MaxHeap，覆盖了父类的上浮和下沉操作，酌情使用。 def __init__(self): super(MaxHeap, self).__init__() def shiftUp(self,i): currentvalue=self.heapList[i] while i//2 > 0: if self.heapList[i//2] > currentvalue: self.heapList[i]=self.heapList[i//2] i//2 else: break self.heapList[i] = currentvalue def shiftDown(self,i): currentvalue=self.heapList[i] while i*2<=self.currentSize: mc=self.minChild(i) if currentvalue > self.heapList[mc]: self.heapList[i]=self.heapList[mc] i=mc else: break self.heapList[i]=currentvalue def minChild(self,i): if i*2+1>self.currentSize: return i*2 else: if self.heapList[i*2] <self.heapList[i*2+1]: return i*2 else: return i*2+1 heap=MaxHeap() max=50000 list=[randint(-max,max) for x in range(max)] alist=list[:] blist=list[:] clist=list[:] t1=timeit.Timer('heap.HeapSort(alist)','from __main__ import heap,alist') print('堆排序: %s s' % t1.timeit(number=1)) t2=timeit.Timer('heap.HeapSortInPlace(blist)','from __main__ import heap,blist') print('堆原地排序: %s s' % t2.timeit(number=1)) t3=timeit.Timer('quickSort(clist)','from __main__ import quickSort,clist') print('快速排序: %s s' % t3.timeit(number=1)) 

完整版源代码下载地址：