第27周-python3.5零基础高级项目剖析共07章节27源码

算法基础第一部分算法简单概念算法概念复习：递归时间复杂度空间复杂度2023年3月8日算法基础2什么是算法？算法（Algorithm）：一个计算过程，解决问题的方法2023年3月8日算法基础3算法输入输出复习：递归递归的两个特点：调用自身结束条件看下面几个函数：2023年3月8日算法基础4deffunc1(x):

print(x)

func1(x-1)

deffunc2(x):

ifx>0:

print(x)

func2(x+1)deffunc3(x):

ifx>0:

print(x)

func3(x-1)

deffunc4(x):

ifx>0:

func4(x-1)

print(x)时间复杂度看代码：2023年3月8日算法基础5print('HelloWorld')foriinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

forkinrange(n):

print('HelloWorld')左面四组代码，哪组运行时间最短？用什么方式来体现代码（算法）运行的快慢？时间复杂度类比生活中的一些事件，估计时间：眨一下眼口算“29+68”烧一壶水睡一觉完成一个项目飞船从地球飞出太阳系2023年3月8日算法基础6一瞬间/几毫秒几秒几分钟几小时几天/几星期/几个月几年时间复杂度时间复杂度：用来评估算法运行效率的一个东西2023年3月8日算法基础7print('HelloWorld')foriinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

forkinrange(n):

print('HelloWorld')O(n2)O(n)O(1)O(n3)时间复杂度那这些代码呢？2023年3月8日算法基础8print('HelloWorld')print('HelloPython')print(‘Hello

Algorithm’)foriinrange(n):print('HelloWorld’)

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(i):

print('HelloWorld')O(3)O(n2+n)O(1/2n2)O(1)O(n2)O(n2)时间复杂度2023年3月8日算法基础9那这个代码呢？whilen>1:

print(n)

n=n//2n=64输出：64321684226=64log264=6O(log2n)或O(logn)时间复杂度-小结时间复杂度是用来估计算法运行时间的一个式子（单位）。一般来说，时间复杂度高的算法比复杂度低的算法快。常见的时间复杂度（按效率排序）O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)不常见的时间复杂度（看看就好）O(n!)

O(2n)

O(nn)

…如何一眼判断时间复杂度？循环减半的过程O(logn)几次循环就是n的几次方的复杂度2023年3月8日算法基础10空间复杂度空间复杂度：用来评估算法内存占用大小的一个式子“空间换时间”2023年3月8日算法基础11列表查找列表查找：从列表中查找指定元素输入：列表、待查找元素输出：元素下标或未查找到元素顺序查找从列表第一个元素开始，顺序进行搜索，直到找到为止。二分查找从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。2023年3月8日算法基础12二分查找2023年3月8日算法基owhighmidmidmid使用二分查找来查找3列表查找-代码2023年3月8日算法基础14deflinear_search(data_set,value):

foriinrange(range(data_set)):

ifdata_set[i]==value:

returni

returndefbin_search(data_set,value):

low=0

high=len(data_set)-1

whilelow<=high:

mid=(low+high)//2

ifdata_set[mid]==value:

returnmid

elifdata_set[mid]>value:

high=mid-1

else:

low=mid+1时间复杂度O(n)O(logn)列表查找：练习现有一个学员信息列表（按id增序排列），格式为：修改二分查找代码，输入学生id，输出该学生在列表中的下标，并输出完整学生信息。2023年3月8日算法基础15[{id:1001,name:"张三",age:20},{id:1002,name:"李四",age:25},{id:1004,name:"王五",age:23},{id:1007,name:"赵六",age:33}]列表排序列表排序将无序列表变为有序列表应用场景：各种榜单各种表格给二分排序用给其他算法用输入：无序列表输出：有序列表2023年3月8日算法基础16排序low

B三人组：冒泡排序选择排序插入排序快速排序排序NB二人组：堆排序归并排序没什么人用的排序：基数排序希尔排序桶排序排序Low

B三人组大家自己能想到怎么完成一次排序吗？冒泡排序选择排序插入排序算法关键点：有序区无序区2023年3月8日算法基础17冒泡排序思路首先，列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数……会发生什么？2023年3月8日算法基础18754638291012345678冒泡排序代码2023年3月8日算法基础19defbubble_sort(li):

foriinrange(len(li)-1):

forjinrange(len(li)-i-1):

ifli[j]>li[j+1]:

li[j],li[j+1]=li[j+1],li[j]时间复杂度：O(n2)冒泡排序-优化2023年3月8日算法基础20defbubble_sort_1(li):

foriinrange(len(li)-1):

exchange=False

forjinrange(len(li)-i-1):

ifli[j]>li[j+1]:

li[j],li[j+1]=li[j+1],li[j]

exchange=True

ifnotexchange:

return如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。选择排序思路一趟遍历记录最小的数，放到第一个位置；再一趟遍历记录剩余列表中最小的数，继续放置；……问题是：怎么选出最小的数？2023年3月8日算法基础21选择排序代码时间复杂度：O(n2)2023年3月8日算法基础22defselect_sort(li):

foriinrange(len(li)-1):

min_loc=i

forjinrange(i+1,len(li)):

ifli[j]<li[min_loc]:

min_loc=j

ifmin_loc!=i:

li[i],li[min_loc]=li[min_loc],li[i]插入排序思路列表被分为有序区和无序区两个部分。最初有序区只有一个元素。每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。2023年3月8日算法基础23574631298插入排序代码时间复杂度：O(n2)优化空间：应用二分查找来寻找插入点（并没有什么卵用）2023年3月8日算法基础24definsert_sort(li):

foriinrange(1,len(li)):

tmp=li[i]

j=i-1

whilej>=0andtmp<li[j]:

li[j+1]=li[j]

j=j-1

li[j+1]=tmp小结——排序LOW

B三人组冒泡排序插入排序选择排序时间复杂度：O(n2)空间复杂度：O(1)练习：尝试自己写一遍这三种排序方式的代码对于前面给出的学生信息列表，使用冒泡排序对其进行升序排序2023年3月8日算法基础25快速排序快速排序：快好写的排序算法里最快的快的排序算法里最好写的2023年3月8日算法基础26快速排序思路快排思路：取一个元素p（第一个元素），使元素p归位；列表被p分成两部分，左边都比p小，右边都比p大；递归完成排序。2023年3月8日算法基础27574631298123456789214356798排序前：目标：P归位：算法关键点：整理递归快速排序代码——第一步defquick_sort(data,left,right):

ifleft<right:

mid=partition(data,left,right)

quick_sort(data,left,mid-1)

quick_sort(data,mid+1,right)2023年3月8日算法基础28怎么写partition函数2023年3月8日算法基础29574631298574631298214356798快速排序代码——第二步defpartition(data,left,right):

tmp=data[left]

whileleft<right:

whileleft<rightanddata[right]>=tmp:

right-=1

data[left]=data[right]

whileleft<rightanddata[left]<=tmp:

left+=1

data[right]=data[left]

data[left]=tmp

returnleft2023年3月8日算法基础30还不理解partition函数？defpartition(data,left,right):

tmp=data[left]

whileleft<right:

whileleft<rightanddata[right]>=tmp:

right-=1

data[left]=data[right]

whileleft<rightanddata[left]<=tmp:

left+=1

data[right]=data[left]

data[left]=tmp

returnleft2023年3月8日算法基础31574631298跟着我右手左手一个慢动作右手左手慢动作重播快速排序-如何效率快速排序真的比冒泡排序快吗？为什么快了？快了多少？问题最坏情况递归2023年3月8日算法基础32快速排序-练习如果想将列表进行降序排序，应该修改哪些符号？还是对于刚才那个学生信息表，修改快速排序代码，使其能够进行排序。2023年3月8日算法基础33堆排序前传——树与二叉树简介树是一种数据结构比如：目录结构树是一种可以递归定义的数据结构树是由n个节点组成的集合：如果n=0，那这是一棵空树；如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。一些概念根节点、叶子节点树的深度（高度）树的度孩子节点/父节点子树2023年3月8日算法基础34特殊且常用的树——二叉树二叉树：度不超过2的树（节点最多有两个叉）2023年3月8日算法基础35两种特殊二叉树满二叉树完全二叉树2023年3月8日算法基础36二叉树的存储方式链式存储方式顺序存储方式（列表）父节点和左孩子节点的编号下标有什么关系？0-1

1-3

2-5

3-7

4-9父节点和右孩子节点的编号下标有什么关系？0-2

1-4

2-6

3-8

4-10比如，我们要找根节点左孩子的左孩子2023年3月8日算法基础37987210563498765012430123456789i

–

2i+1i

–

2i+2二叉树小结二叉树是度不超过2的树满二叉树与完全二叉树（完全）二叉树可以用列表来存储，通过规律可以从父亲找到孩子或从孩子找到父亲2023年3月8日算法基础38堆排序堆大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小2023年3月8日算法基础39堆排序2023年3月8日算法基础409872105634大根堆：1264975386小根堆：堆这个玩意…2023年3月8日算法基础412976105384假设：节点的左右子树都是堆，但自身不是堆当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆。堆排序过程建立堆得到堆顶元素，为最大元素去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。堆顶元素为第二大元素。重复步骤3，直到堆变空。2023年3月8日算法基础42构造堆2023年3月8日算法基础436812703954挨个出数2023年3月8日算法基础449872105634堆排序代码2023年3月8日算法基础45defsift(data,low,high):

i=low

j=2*i+1

tmp=data[i]

whilej<=high:

ifj<highanddata[j]<data[j+1]:

j+=1

iftmp<data[j]:

data[i]=data[j]

i=j

j=2*i+1

else:

break

data[i]=tmpdefheap_sort(data):

n=len(data)

foriinrange(n//2-1,-1,-1):

sift(data,i,n-1)

foriinrange(n-1,-1,-1):

data[0],data[i]=data[i],data[0]

sift(data,0,i-1)归并排序假设现在的列表分两段有序，如何将其合成为一个有序列表这种操作称为一次归并。2023年3月8日算法基础46253178694一次归并代码defmerge(li,low,mid,high):

i=low

j=mid+1

ltmp=[]

whilei<=midandj<=high:

ifli[i]<=li[j]:

ltmp.append(li[i])

i+=1

else:

ltmp.append(li[j])

j+=1

whilei<=mid:

ltmp.append(li[i])

i+=1

whilej<=high:

ltmp.append(li[j])

j+=1

li[low:high+1]=ltmp2023年3月8日算法基础47有了归并怎么用？分解：将列表越分越小，直至分成一个元素。一个元素是有序的。合并：将两个有序列表归并，列表越来越大。2023年3月8日算法基础48归并排序defmergesort(li,low,high):

iflow<high:

mid=(low+high)//2

mergesort(li,low,mid)

mergesort(li,mid+1,high)

merge(li,low,mid,high)2023年3月8日算法基础49时间复杂度：O(nlogn)空间复杂度：O(n)快速排序、堆排序、归并排序-小结三种排序算法的时间复杂度都是O(nlogn)一般情况下，就运行时间而言：快速排序<归并排序<堆排序三种排序算法的缺点：快速排序：极端情况下排序效率低归并排序：需要额外的内存开销堆排序：在快的排序算法中相对较慢2023年3月8日算法基础50希尔排序思路希尔排序是一种分组插入排序算法。首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。2023年3月8日算法基础51574631298d=4d=2d=1希尔排序defshell_sort(li):

gap=len(li)//2

whilegap>0:

foriinrange(gap,len(li)):

tmp=li[i]

j=i-gap

whilej>=0andtmp<li[j]:

li[j+gap]=li[j]

j-=gap

li[j+gap]=tmp

gap/=22023年3月8日算法基础52时间复杂度： O((1+τ)n)

O(1.3n)排序-小结排序方法时间复杂度稳定性代码复杂度最坏情况平均情况最好情况冒泡排序O(n2)O(n2)O(n)稳定简单直接选择排序O(n2)O(n2)O(n2)不稳定简单直接插入排序O(n2)O(n2)O(n2)稳定简单快速排序O(n2)O(nlogn)O(nlogn)不稳定较复杂堆排序O(nlogn)O(nlogn)O(nlogn)不稳定复杂归并排序O(nlogn)O(nlogn)O(nlogn)稳定较复杂希尔排序O(1.3n)不稳定较复杂2023年3月8日算法基础53排序-赠品1现在有一个列表，列表中的数范围都在0到100之间，列表长度大约为100万。设计算法在O(n)时间复杂度内将列表进行排序。2023年3月8日算法基础54赠品1-计数排序创建一个列表，用来统计每个数出现的次数。2023年3月8日算法基础55defcount_sort(li,max_num):

count=[0foriinrange(max_num+1)]

fornuminli:

count[num]+=1

i=0

fornum,minenumerate(count):

forjinrange(m):

li[i]=num

i+=1排序-赠品2现在有n个数（n>10000），设计算法，按大小顺序得到前10大的数。应用场景：榜单TOP

102023年3月8日算法基础56赠品2-堆的应用（了解）解决思路：取列表前10个元素建立一个小