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

算法基础第一部分算法简单概念算法概念复习：递归时间复杂度空间复杂度2023年2月14日算法基础2什么是算法？算法（Algorithm）：一个计算过程，解决问题的方法2023年2月14日算法基础3算法输入输出复习：递归递归的两个特点：调用自身结束条件看下面几个函数：2023年2月14日算法基础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年2月14日算法基础5print('HelloWorld')foriinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

forkinrange(n):

print('HelloWorld')左面四组代码，哪组运行时间最短？用什么方式来体现代码（算法）运行的快慢？时间复杂度类比生活中的一些事件，估计时间：眨一下眼口算“29+68”烧一壶水睡一觉完成一个项目飞船从地球飞出太阳系2023年2月14日算法基础6一瞬间/几毫秒几秒几分钟几小时几天/几星期/几个月几年时间复杂度时间复杂度：用来评估算法运行效率的一个东西2023年2月14日算法基础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年2月14日算法基础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年2月14日算法基础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年2月14日算法基础10空间复杂度空间复杂度：用来评估算法内存占用大小的一个式子“空间换时间”2023年2月14日算法基础11列表查找列表查找：从列表中查找指定元素输入：列表、待查找元素输出：元素下标或未查找到元素顺序查找从列表第一个元素开始，顺序进行搜索，直到找到为止。二分查找从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。2023年2月14日算法基础12二分查找2023年2月14日算法基owhighmidmidmid使用二分查找来查找3列表查找-代码2023年2月14日算法基础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年2月14日算法基础15[{id:1001,name:"张三",age:20},{id:1002,name:"李四",age:25},{id:1004,name:"王五",age:23},{id:1007,name:"赵六",age:33}]列表排序列表排序将无序列表变为有序列表应用场景：各种榜单各种表格给二分排序用给其他算法用输入：无序列表输出：有序列表2023年2月14日算法基础16排序low

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

B三人组大家自己能想到怎么完成一次排序吗？冒泡排序选择排序插入排序算法关键点：有序区无序区2023年2月14日算法基础17冒泡排序思路首先，列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数……会发生什么？2023年2月14日算法基础18754638291012345678冒泡排序代码2023年2月14日算法基础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年2月14日算法基础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年2月14日算法基础21选择排序代码时间复杂度：O(n2)2023年2月14日算法基础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年2月14日算法基础23574631298插入排序代码时间复杂度：O(n2)优化空间：应用二分查找来寻找插入点（并没有什么卵用）2023年2月14日算法基础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年2月14日算法基础25快速排序快速排序：快好写的排序算法里最快的快的排序算法里最好写的2023年2月14日算法基础26快速排序思路快排思路：取一个元素p（第一个元素），使元素p归位；列表被p分成两部分，左边都比p小，右边都比p大；递归完成排序。2023年2月14日算法基础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年2月14日算法基础28怎么写partition函数2023年2月14日算法基础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年2月14日算法基础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年2月14日算法基础31574631298跟着我右手左手一个慢动作右手左手慢动作重播快速排序-如何效率快速排序真的比冒泡排序快吗？为什么快了？快了多少？问题最坏情况递归2023年2月14日算法基础32快速排序-练习如果想将列表进行降序排序，应该修改哪些符号？还是对于刚才那个学生信息表，修改快速排序代码，使其能够进行排序。2023年2月14日算法基础33堆排序前传——树与二叉树简介树是一种数据结构比如：目录结构树是一种可以递归定义的数据结构树是由n个节点组成的集合：如果n=0，那这是一棵空树；如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。一些概念根节点、叶子节点树的深度（高度）树的度孩子节点/父节点子树2023年2月14日算法基础34特殊且常用的树——二叉树二叉树：度不超过2的树（节点最多有两个叉）2023年2月14日算法基础35两种特殊二叉树满二叉树完全二叉树2023年2月14日算法基础36二叉树的存储方式链式存储方式顺序存储方式（列表）父节点和左孩子节点的编号下标有什么关系？0-1

1-3

2-5

3-7

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

1-4

2-6

3-8

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

–

2i+1i

–

2i+2二叉树小结二叉树是度不超过2的树满二叉树与完全二叉树（完全）二叉树可以用列表来存储，通过规律可以从父亲找到孩子或从孩子找到父亲2023年2月14日算法基础38堆排序堆大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小2023年2月14日算法基础39堆排序2023年2月14日算法基础409872105634大根堆：1264975386小根堆：堆这个玩意…2023年2月14日算法基础412976105384假设：节点的左右子树都是堆，但自身不是堆当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆。堆排序过程建立堆得到堆