冒泡算法
1 a=[1, 2, 6, 22, 44, 12, 4] 2 for j in range(len(a)): 3 for i in range(1, len(a)-j): 4 if a[i-1]>a[i]: 5 a[i-1], a[i]=a[i], a[i-1]
快速排序`
1 items=[10, 33, 34, 3, 1, 2, 4, 5, 77, 29] 2 3 def quick_sort(i, j): 4 if i>j: 5 return 6 temp=items[i] 7 left=i 8 right=j 9 while i!=j: 10 while items[j]>temp and i<j: 11 j-=1 #有可能大于j? 12 while items[i]<=temp and i<j: 13 i+=1 #i, j都是1 #j=0 ,i=1 14 items[j], items[i]=items[i], items[j] 15 items[left], items[j]=items[j], items[left] 16 17 print(items) 18 quick_sort(i=left, j=j-1) #i=0 j=0 ; i=0, j=-1 19 quick_sort(i=j+1, j=right) 20 21 quick_sort(i=0, j=len(items)-1)
虽然可以通过归纳法总结出 quick_sort(i=left, j=j-1)的i和j的值以及quick_sort(i=j+1, j=right)中的i和j的值,但是仍存在的问题是我依然不知道是怎么想出来的,递归的方法是怎么相处来的
归并排序
1 def mergesort(seq): 2 if len(seq)<=1: 3 return seq 4 mid=len(seq)/2 5 left=mergesort(seq[:mid]) 6 right=mergesort(seq[mid:]) 7 return merge(left, right) 8 9 def merge(left, right): 10 i=0 11 j=0 12 result=[] 13 while i<len(left) and j<len(right): 14 if left[i]<=right[j]: 15 result.append(left[i]) 16 i+=1 17 else: 18 result.append(right[j]) 19 j+=1 20 result+=left[i:] 21 result+=right[j:] 22 return result 23 24 #seq = [4, 8, 6, 9, 7, 5, 1, 0, 7, -2, 3, -99, 6] 25 seq = ['d', 'a', 'h', 'g', 'a'] 26 print (mergesort(seq))
堆排序
1 #二叉堆 2 #最大堆 (父结点的键值总是大于或等于任何(这里的任何一个节点指的是父节点下的子节点)一个子节点的键值) 3 #最小堆 (父结点的键值总是小于或等于任何(这里的任何一个节点指的是父节点下的子节点)一个子节点的键值) 4 class BinHeap: 5 def __init__(self): 6 self.heapList = [0] 7 self.currentSize = 0 8 9 def percUp(self, i): 10 #从第一层开始 11 while i//2>0: 12 if self.heapList[i//2]>self.heapList[i]: 13 self.heapList[i//2], self.heapList[i]=self.heapList[i], self.heapList[i//2] 14 i //= 2 15 16 def percDown(self, i): 17 while (i * 2) <= self.currentSize: 18 print(u"i的值是{0}".format(i)) 19 mc = self.minChild(i) 20 print (u'mc的值是{0}'.format(mc)) 21 if self.heapList[i] > self.heapList[mc]: 22 tmp = self.heapList[i] 23 self.heapList[i] = self.heapList[mc] 24 self.heapList[mc] = tmp 25 i = mc 26 print (u'二叉堆的值是{0}'.format(Btree.heapList))#这一步是怎么来的 27 28 29 # def percDown(self, i): 30 # """ 31 # 自上而下 32 # """ 33 # while self.currentSize >= (2*i): 34 # mc=self.minChild(i) 35 # if self.heapList[i]>self.heapList[mc]: 36 # self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i] 37 # i=mc 38 39 40 def minChild(self, i): 41 if self.currentSize<(2*i+1): 42 return 2*i 43 else: 44 if self.heapList[2*i] > self.heapList[2*i+1]: 45 return 2*i+1 46 else: 47 return 2*i 48 49 def insert(self, x): 50 self.heapList.append(x) 51 self.currentSize+=1 52 self.percUp(self.currentSize) 53 54 def delMin(self): 55 del_element=self.heapList[1] 56 self.heapList[1]=self.heapList[self.currentSize] 57 self.currentSize=self.currentSize-1 58 self.heapList.pop() 59 self.percDown(1) 60 return del_element 61 62 def buildHeap(self, alist): 63 i = len(alist) // 2 64 self.currentSize = len(alist) 65 self.heapList = [0] + alist[:] 66 while i > 0: 67 self.percDown(i) 68 i -=1 69 70 71 Btree=BinHeap() 72 Btree.insert(4) 73 Btree.insert(6) 74 Btree.insert(7) 75 Btree.insert(9) #这里存在疑问 76 Btree.insert(10) 77 Btree.insert(15) #这里可以改成11,15 78 Btree.insert(12) 79 Btree.insert(13) 80 Btree.insert(14) 81 82 print ("原来的数值{0}".format(Btree.heapList)) 83 print (Btree.delMin()) 84 print ('后来的数值{0}'.format(Btree.heapList)) 85 86 Btree.buildHeap([2, 32, 4, 23, 3, 56, 11]) 87 print ('新建数值{0}'.format(Btree.heapList))