1.1翻转一个字符串

切蛋糕思维
image.png

  1. def str_reverse(str,end):
  2.     end-=1
  3.     if end==0:
  4.         return str
  5.     t=list(str)    #str[i]是错误的，和其他语言不一样
  6.     return t[end]+str_reverse(str[:-1],end)  #str[:-1]表示切取0至倒数第1个字符（不包括），所以就是丢掉最后一个字符
  8. str='abc'
  9. print(str_reverse(str,3))

1.2斐波拉契数

递推公式或者等价转换
image.png

  1. def fei(n):
  2.     if n==1 or n==2:
  3.         return 1
  4.     return fei(n-1)+fei(n-2)
  6. print(fei(5))

1.3求两个整数的最大公约数

递推公式
image.png

  1. def max_com_divisor(m,n):
  2.     if(n==0):
  3.         return m
  4.     return max_com_divisor(n,m%n)
  6. print(max_com_divisor(8,3))

1.4插入排序(o(n^2))

RPReplay_Final1575811816.mp4 (244.17KB)

  1. import random
  2. import time
  3. def insert_sort(alist):
  4.     for i in range(1,len(alist)):
  5.         j=i
  6.         while j>0:
  7.             if alist[j]<alist[j-1]:
  8.                 alist[j-1],alist[j]=alist[j],alist[j-1]  #交换使得赋值次数为3
  9.                 j-=1
  10.             else:
  11.                 break
  15. alist=random.sample(range(0,10000),10000)
  16. start=time.clock()
  17. insert_sort(alist)
  18. end=time.clock()
  19. print(end-start)

改进的插入排序

  1. import random
  2. import time
  3. def insert_sort(alist):
  4.     for i in range(1,len(alist)):
  5.         j=i
  6.         e=alist[j] #将每次要插入的数赋给e
  7.         while j>0:
  8.             if e<alist[j-1]:
  9.                 alist[j]=alist[j-1]  #不做交换，只做一次赋值
  10.                 j-=1
  11.             else:
  12.                 break
  16. alist=random.sample(range(0,10000),10000)
  17. start=time.clock()
  18. insert_sort(alist)
  19. end=time.clock()
  20. print(end-start)

用递归插入升序排序数组

  1. def insert_sort(alist,n):
  2.     n=n-1
  3.     if n==0:
  4.         return 
  5.     if n>0:
  6.         insert_sort(alist,n)
  7.         k=n
  8.         while (k>0)and(alist[k]<alist[k-1]):
  9.             alist[k],alist[k-1]=alist[k-1],alist[k]  #交换
  10.             k=k-1
  11.         return alist
  14. alist=[1,4,5,3,7,9,8,0,11,10,2,14]
  15. insert_sort(alist,len(alist))
  16. print(alist)

1.5 汉诺塔

image.png

  1. def hannota(N,start,distination,assistance):
  2.     count=0
  3.     N=int(N)
  4.     if N<=1:
  5.         print("move"+str(N)+"from"+start+"to"+distination)
  6.         return 1 
  7.     count+=hannota(N-1,start,assistance,distination)
  8.     print("move"+str(N)+"from"+start+"to"+distination)
  9.     count+=1
  10.     count+=hannota(N-1,assistance,distination,start)
  11.     return count
  12. a='A'
  13. b='B'
  14. c='C'
  15. print(hannota(3,a,b,c))
  16. move1fromAtoB
  17. move2fromAtoC
  18. move1fromBtoC
  19. move3fromAtoB
  20. move1fromCtoA
  21. move2fromCtoB
  22. move1fromAtoB
  23. 7

1.7二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

  1. def erfensearch(alist,low,high,key):
  2.     if low>high:
  3.         return -1
  4.     elif low==high:
  5.         if alist[low]==key:
  6.             return low
  8.     else:
  9.         mid = (low+high)>>1
  10.         if alist[mid]>key:
  11.             return erfensearch(alist,low,mid-1,key)
  12.         elif alist[mid]<key:
  13.             return erfensearch(alist,mid+1,high,key)
  15.         else:
  16.             return mid
  19. alist=[1,2,3,4,5,6,7,8]
  20. print(erfensearch(alist,0,len(alist)-1,4))

1.8归并排序

借助辅助空间，时间复杂度为nlogn

RPReplay_Final1575979198.mp4 (195.78KB)

  1. import random
  2. import time
  3. def merge(alist,left,mid,right):
  4.     blist=[0]
  5.     blist[0]=alist[left]
  6.     for i in range(left+1,right+1):
  7.         blist.append(alist[i])        #创建辅助数组
  9.     i=left
  10.     j=mid+1
  11.     for k in range(left,right+1):
  12.         if i>mid:                     #i>mid,j>right都是溢出情况
  13.             alist[k]=blist[j-left]
  14.             j+=1
  15.         elif j>right:
  16.             alist[k]=blist[i-left]
  17.             i+=1
  18.         else:
  19.             if blist[i-left]<blist[j-left]:
  20.                 alist[k]=blist[i-left]
  21.                 i+=1
  22.             else:
  23.                 alist[k]=blist[j-left]
  24.                 j+=1
  27. def MergeSort(alist,left,right):
  28.     if right>left:
  29.         mid=(left+right)>>1
  30.         MergeSort(alist,left,mid)
  31.         MergeSort(alist,mid+1,right)
  32.         merge(alist,left,mid,right)
  34. alist=random.sample(range(0,30000),30000)
  35. left=1000                #可以从alist中的任何索引开始排序
  36. right=len(alist)-1
  37. start=time.clock()
  38. MergeSort(alist,left,right)
  39. end=time.clock()
  40. print(end-start)
  43. #优化后的归并排序
  44. def MergeSort(alist,left,right):
  45.     if right>left:
  46.         mid=(left+right)>>1
  47.         MergeSort(alist,left,mid)
  48.         MergeSort(alist,mid+1,right)
  49.         if alist[mid]>alist[mid+1]:
  50.             merge(alist,left,mid,right)
  53. #当递归到数据量比较小的时候，可以采用插入排序，此时数据近乎有序的几率比较大，对于近乎有序的数据，
  54. #插入排序的时间比归并排序的时间短
  55. def MergeSort(alist,left,right):
  56.     if right-left<=15:
  57.         insert_sort(alist,left,right)
  58.         return 
  60.     mid=(left+right)>>1
  61.     MergeSort(alist,left,mid)
  62.     MergeSort(alist,mid+1,right)
  63.     if alist[mid]>alist[mid+1]:
  64.          merge(alist,left,mid,right)
  67. #自底向上的的归并排序
  68. def MergeSort(alist,n):
  69.     sz=1
  70.     i=0
  71.     while sz<=n:
  72.         while i+sz<n:
  73.             #对alist[i...i+sz-1]和alist[i+sz...i+2*sz-1]进行归并
  74.             merge(alist,i,i+sz-1,min(i+sz+sz-1,n-1))
  75.             i+=sz^2
  77.         sz+=sz

利用归并排序求逆序对

  1. import random
  2. import time
  3. def merge(alist,left,mid,right):
  6.     blist=[0]  
  7.     blist[0]=alist[left]
  8.     for i in range(left+1,right+1):
  9.         blist.append(alist[i])        #创建辅助数组
  10.     global n
  11.     i=left
  12.     j=mid+1
  13.     for k in range(left,right+1):
  15.         if i>mid:
  16.             alist[k]=blist[j-left]
  17.             j+=1
  18.         elif j>right:
  19.             alist[k]=blist[i-left]
  20.             i+=1
  21.         else:
  22.             if blist[i-left]<blist[j-left]:
  23.                 alist[k]=blist[i-left]
  24.                 i+=1
  25.             else:
  26.                 alist[k]=blist[j-left]
  27.                 j+=1
  28.                 n=n+(mid-i+1)  #求逆序对数
  30.     print(alist)
  31. def MergeSort(alist,left,right):
  32.     global n
  33.     if right>left:
  34.         mid=(left+right)>>1
  35.         MergeSort(alist,left,mid)
  36.         MergeSort(alist,mid+1,right)
  37.         merge(alist,left,mid,right)
  39. alist=random.sample(range(0,8),8)
  40. n=0
  42. print(alist)
  44. print("----------")
  45. left=0
  46. right=len(alist)-1
  47. start=time.clock()
  48. MergeSort(alist,left,right)
  49. print(n)
  50. end=time.clock()
  51. print(end-start)

1.9快速排序

时间复杂度为nlogn

  1. def sure_k(alist,low,high):
  2.     k=low
  3.     x=alist[low]
  4.     for i in range(low+1,high+1):
  5.         if alist[i]<=x:
  6.             k+=1
  7.             if k!=i:
  8.                 alist[k],alist[i]=alist[i],alist[k]
  10.     alist[low],alist[k]=alist[k],alist[low]
  11.     print(alist,"---",alist[k])
  12.     return k
  14. def quicksort(alist,low,high):
  15.     if high-low<=15:
  16.         insert_sort(alist,low,high)
  17.     k=sure_k(alist,low,high)
  18.     quicksort(alist,low,k-1)
  19.     quicksort(alist,k+1,high)
  20.     else:
  21.         return
  23. alist=[5,1,3,8,0,4,7,2,7,9,6,10,14,13]
  24. print(alist)
  25. quicksort(alist,0,len(alist)-1)

快速二路排序
**

  2. #采用赋值而不是交换的方式
  3. import random
  4. import time
  5. def partition(alist,left,right):
  7.     e=alist[left]
  8.     if left>right:
  9.         return 
  10.     while (left<right):
  11.         while (alist[right]>e)&(right>left):
  12.             right-=1
  13.         if (alist[right]<e)&(left<right):
  14.             alist[left]=alist[right]
  15.         while (alist[left]<e)&(left<right):
  16.             left+=1
  17.         if (alist[left]>e)&(left<right):
  18.             alist[right]=alist[left]
  20.     alist[left]=e
  23.     k=left
  24.     return k
  26. def partition_sort(alist,left,right):
  27.     if left>right:
  28.         return 
  29.     k=partition(alist,left,right)
  30.     partition_sort(alist,left,k-1)
  31.     partition_sort(alist,k+1,right)
  34. alist=random.sample(range(0,10000),10000)
  35. print(alist)
  36. start=time.clock()
  37. partition_sort(alist,0,9999)
  38. end=time.clock()
  39. print(end-start)

三路快速排序：当一个数组中有比较多的相同数时适用

  1. import random 
  2. import time
  3. import sys   
  4. sys.setrecursionlimit(1000000)
  6. def quick_sort(alist,left,right):
  7.     if right-left<1:
  8.         return 
  9.     v=alist[left]
  10.     lt=left
  11.     gt=right
  12.     i=left+1
  13.     while i<gt:
  14.         if alist[i]>v:
  15.             alist[i],alist[gt]=alist[gt],alist[i]
  16.             gt-=1
  17.         elif alist[i]<v:
  18.             alist[i],alist[lt+1]=alist[lt+1],alist[i]
  19.             i+=1
  20.             lt+=1
  21.         else:
  22.             i+=1
  24.     alist[left],alist[lt]=alist[lt],alist[left]
  26.     quick_sort(alist,left,lt-1)
  27.     quick_sort(alist,gt,right)
  32. alist=random.sample(range(0,10000),10000)
  33. x=1000
  34. while x:
  35.     alist.append(alist[0])
  36.     x-=1
  37. start=time.clock()
  38. quick_sort(alist,0,len(alist)-1)
  39. end=time.clock()
  40. print(end-start)

利用快速排序查找数组中第k大的数

  1. import random 
  2. import time
  3. import sys   
  4. sys.setrecursionlimit(1000000)
  6. def partition(alist,left,right):
  8.     e=alist[left]
  9.     while (left<right):
  10.         while (alist[right]>e)&(right>left):
  11.             right-=1
  12.         if (alist[right]<e)&(left<right):
  13.             alist[left]=alist[right]
  14.         while (alist[left]<e)&(left<right):
  15.             left+=1
  16.         if (alist[left]>e)&(left<right):
  17.             alist[right]=alist[left]
  19.     alist[left]=e
  22.     k=left
  23.     return k
  25. def partition_sort(alist,left,right,v):
  27.     if (left>=right) & (left == v):
  28.         return alist[v]
  29.     k=partition(alist,left,right)
  31.     if k>v:
  32.         return partition_sort(alist,left,k-1,v)
  34.     elif k<v:
  35.        return  partition_sort(alist,k+1,right,v)
  37.     else:
  39.         return alist[k]
  40. alist=random.sample(range(0,30000),30000)
  41. k=partition_sort(alist,0,len(alist)-1,10000)
  42. print(k)

1.10优先队列

概念

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。
image.png
image.png

实现

通常采用堆数据结构来实现。

image.png

堆的定义

堆其实就是一棵完全二叉树（若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边），
定义为：具有n个元素的序列（h1,h2,…hn），当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,…,n/2)时称之为堆

image.png

堆排序

  1. import random
  2. import time
  4. class MaxHeap(object):
  6.     def __init__(self):
  7.         self._data = []
  8.         self._count = len(self._data)
  10.     def size(self):
  11.         return self._count
  13.     def isEmpty(self):
  14.         return self._count == 0
  16.     def add(self, item):
  17.         # 插入元素入堆
  18.         self._data.append(item)
  19.         self._count += 1
  20.         self._shiftup(self._count-1)     #堆的序号从0开始
  22.     def pop(self):
  23.         # 出堆
  24.         if self._count > 0:
  25.             ret = self._data[0]
  27.             self._data[0] = self._data[self._count-1]  #移除堆的最顶的元素
  28.             self._count -= 1 
  30.             self._shiftDown(0)    #对移除之后的堆进行排序，使之成为最大堆
  31.             return ret
  33.     def _shiftup(self, index):
  34.         # 上移self._data[index]，以使它不大于父节点
  35.         parent = (index-1)>>1
  36.         while index > 0 and self._data[parent] < self._data[index]:
  37.             # swap
  38.             self._data[parent], self._data[index] = self._data[index], self._data[parent]
  39.             index = parent
  40.             parent = (index-1)>>1
  42.     def _shiftDown(self, index):
  43.         # 上移self._data[index]，以使它不小于子节点
  44.         j = (index << 1) + 1
  45.         while j < self._count :
  46.             # 有子节点
  47.             if j+1 < self._count and self._data[j+1] > self._data[j]:
  48.                 # 有右子节点，并且右子节点较大
  49.                 j += 1
  50.             if self._data[index] >= self._data[j]:
  51.                 # 堆的索引位置已经大于两个子节点，不需要交换了
  52.                 break
  53.             self._data[index], self._data[j] = self._data[j], self._data[index]
  54.             index = j
  55.             j = (index << 1) + 1
  57.     def MaxHeap1(self,alist,n):  #n表示alist的长度
  58.         self._data=n*[0]
  59.         for i in range(0,n):
  60.             self._data[i]=alist[i]
  61.         self._count=n
  62.         i=(self._count-1)>>2
  63.         while i>=0:
  64.             self._shiftDown(i)
  65.             i-=1
  67. #通过将数组的数一个一个添加到堆中然后在移出堆的操作实现逆序
  68. def Heapsort1(alist):
  69.     maxheap=MaxHeap()
  70.     for i in range(0,len(alist)):
  71.         maxheap.add(alist[i])
  72.     i=maxheap._count-1
  73.     while i>=0:
  74.         alist[i]=maxheap.pop()
  75.         i-=1
  77. #通过开辟一个与数组同长度的堆，然后赋值->shitfdown使得成为最大堆，最后移出堆操作实现逆序
  78. def Heapsort2(alist):
  79.     #开辟新空间maxheap
  80.     maxheap=MaxHeap()
  81.     maxheap.MaxHeap1(alist,len(alist))
  82.     i=len(alist)-1
  83.     while i>=0:
  84.         alist[i]=maxheap.pop()
  85.         i-=1
  87. #直接对alist逆排序，不创建堆空间
  88. def Heapsort3(alist):
  89.     #对数组heapify
  90.     i=(len(alist)-1)>>1
  91.     while i>=0:
  92.         shiftdown(alist,len(alist),i)
  93.         i-=1
  94.     #对数组进行逆序
  95.     k=len(alist)-1
  96.     while k>0:
  97.         #交换
  98.         alist[k],alist[0]=alist[0],alist[k]
  99.         shiftdown(alist,k,0)
  100.         k-=1
  101. def shiftdown(alist,n,k):
  102.     while 2*k+1<n:   #当左孩子没有越界
  103.         j=2*k+1
  104.         if j+1<n and alist[j+1]>alist[j]:
  105.             j+=1
  106.         if alist[k]>=alist[j]:
  107.             break
  108.         alist[k],alist[j]=alist[j],alist[k]
  109.         k=j
  112. if __name__ == '__main__':
  113.     alist=random.sample(range(0,10000),10000)
  114.     start=time.clock()
  115.     Heapsort3(alist)
  116.     end=time.clock()
  117.     print(end-start)

索引堆

image.png

  1. import math
  2. class IndexMaxHeap(object):
  4.     def __init__(self,capacity):
  5.         self._indexes =capacity*[0]
  6.         self._data=capacity*[0]
  7.         self._reverse=capacity*[0]
  8.         self._count = 0
  12.     def size(self):
  13.         return self._count
  15.     def isEmpty(self):
  16.         return self._count == 0
  18.     def IndexMaxHeap1(self,alist):
  19.         for i in range(0,len(alist)):
  20.             self._data[i]=alist[i]
  21.             self._indexes[i]=i
  22.             self._reverse[i]=i
  23.             self._count+=1
  24.         #进行最大堆排序
  25.         i=(self._count-2)>>1 #求第一个不是叶子节点的元素的序号
  26.         while i>=0:
  27.             self._shiftDown(i)
  28.             i-=1
  31.     #传入的i对用户而言，是从0索引的
  32.     def add(self, i,item):
  33.         # 插入元素入堆
  34.         self._data.append(item)
  35.         self._indexes.append(i)
  36.         self._reverse.append(self._count)
  37.         self._count += 1
  40.         self._shiftup(self._count-1)     #堆的序号从0开始
  43.     def pop(self):
  44.         # 出堆,返回的是堆的最大元素
  45.         if self._count > 0:
  46.             ret = self._data[self._indexes[0]] 
  48.             self._indexes[0],self._indexes[self._count-1]= self._indexes[self._count-1],self._indexes[0]  #移除堆的最顶的元素
  49.             self._reverse[self._indexes[0]]=0   
  50.             self._reverse[self._indexes[count-1]]=0
  51.             self._count -= 1 
  53.             self._shiftDown(0)    #对移出之后的堆进行排序，使之成为最大堆
  54.             return ret
  56.     def popindex(self):
  57.         #返回最大元素的索引
  58.         if self._count>0:
  59.             ret=self._indexes[0]  #对于用户来说，返回的是从0开始列表最大元素的索引
  60.             self._indexes[0],self._indexes[self._count-1]= self._indexes[self._count-1],self._indexes[0]  #移除堆的最顶的元素
  61.             self._count-=1
  62.             self._shiftDown(0)
  63.             return ret
  65.     def contain(self,i):
  66.         #验证用户传进的i（以0开始）的参数是不是在索引堆中
  67.         if i>=0 and i+1<=self._count:
  68.             return self._reverse[i]!=0
  70.     def getItem(self,i):
  71.         if self.contain(i):
  72.             return self._data[i]
  74.     def change(self,i,item):  #将列表中的data[i]改为item
  75.         if self.contain(i):
  76.             self._data[i]=item
  77.             #找到indexes[j]=i,j表示data[i]在堆中的位置
  78.             # for j in range(0,self._count):
  79.             #     if self._indexes[j]==i:
  80.             #         _shiftup(j)
  81.             #         _shiftDown(j)
  82.             #         return
  83.             j=self._reverse[i]
  84.             self._shiftup(j)
  85.             self._shiftDown(j)
  88.     #上浮和下沉都是入堆与出堆的操作，与用户无关，可以设为私有方法    
  89.     def _shiftup(self, k):
  90.         # 上移self._indexes[k]，以使它不大于父节点
  91.         while k > 0 and self._data[self._indexes[(k-1)>>1]] < self._data[self._indexes[k]]:
  92.             # swap
  93.             self._indexes[(k-1)>>1], self._indexes[k] = self._indexes[k], self._indexes[(k-1)>>1]
  94.             self._reverse[self._indexes[(k-1)>>1]]=(k-1)>>1
  95.             self._reverse[self._indexes[k]]=k
  96.             k=(k-1)>>1
  98.     def _shiftDown(self, k):
  99.         # 上移self._data[index]，以使它不小于子节点
  101.         while (k <<1+1) <= self._count :
  102.             j = k << 1 + 1
  103.             # 有子节点
  104.             if j+1 < self._count and self._data[self._indexes[j+1]] > self._data[self._indexes[j]]:
  105.                 # 有右子节点，并且右子节点较大
  106.                 j += 1
  107.             if self._data[self._indexes[k]] >= self._data[self._indexes[j]]:
  108.                 # 堆的索引位置已经大于两个子节点，不需要交换了
  109.                 break
  110.             self._indexes[k],self._indexes[j]=self._indexes[j],self._indexes[k]
  111.             self._reverse[self._indexes[k]]=k
  112.             self._reverse[self._indexes[j]]=j
  113.             k = j
  117. indexheap=IndexMaxHeap(5)
  118. alist=[30,90,3,6,40]
  119. indexheap.IndexMaxHeap1(alist)
  120. print(indexheap._indexes)
  121. indexheap.add(5,80)
  122. print(indexheap._indexes)  
  123. print(indexheap.getItem(5)) #80

运行结果：
image.png

排序总结

image.png

排序的稳定性

image.png