• ADT Map定义的操作

Map()：创建一个空映射，返回空映射对象；

put(key, val)：将key‐val关联对加入映射中，如果key已存在，将val替换旧关联值；

get(key)：给定key，返回关联的数据值，如不存在，则返回None；

del：通过del map[key]的语句形式删除key‐val关联；

len()：返回映射中key‐val关联的数目；

in：通过key in map的语句形式，返回key是否存在于关联中，布尔值

• ADT Map 的实现实例

#我们用一个HashTable类来实现ADT Map，该类包含了两个列表作为成员

其中一个slot列表用于保存key

另一个平行的data列表用于保存数据项

在slot列表搜索到一个key的位置以后，在data列表对应相同位置的数据项即为关联数据

class HashTable:

def init (self):

self.size = 11

self.slots = [None]*self.size

self.data = [None]*self.size

def hashfunction(self, key):

return key% self.size

def rehash( self, oldhash):

return (oldhash+ 1)% self.size

def put(self,key,data):

hashvalue = self.hashfunction(key)

if self.slots [hashvalue] == None:

self.slots[hashvalue] = key

self.data [hashvalue] = data

else:

if self.slots [hashvalue] == key:

self.data[hashvalue] = data #replace

else:

nextslot = self.rehash(hashvalue)

while self.slots[nextslot] != None and self.slots [nextslot] != key:

nextslot = self.rehash(nextslot)

if self.slots [nextslot] == None:

self . slots[nextslot]=key

self . data [nextslot]=data

else:

self.data[nextslot] = data #replace

def get(self,key):

startslot = self.hashfunction(key) # 标记散列值为搜索起点

data = None

stop = False

found = False

position = startslot

while self.slots[position] != None and not found and not stop:

找key，直到空槽或回到起点

if self.slots[position] == key:

found = True

data = self . data[position]

else:

position=self.rehash( position) # 未找到key，再散列继续找

if position == startslot: # 回到起点 ， 停

stop = True

return data

通过特殊方法实现[]访问

def getitem(self, key):

return self.get(key)

def setitem(self, key, data):

self.put(key, data)

H=HashTable()

H[54]=“cat”

H[26]= “dog”

H[93]=“lion”

H[17]=“tiger”

H[77]=“bird”

H[31]=“cow”

H[44]=“goat”

H[55]=“pig”

H[ 20]= “chicken”

print(H.slots)

print(H.data)

print(H[20])

print(H[17])

H[20]= ‘duck’

print(H[20])

print(H[99])

结果

“”"

[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]

[‘bird’, ‘goat’, ‘pig’, ‘chicken’, ‘dog’, ‘lion’, ‘tiger’, None, None, ‘cow’, ‘cat’]

chicken

tiger

duck

None

“”"

• 散列算法分析

❖ 散列在最好的情况下，可以提供O(1)常数级时间复杂度的搜索性能

由于散列冲突的存在，搜索比较次数就没有这么简单

❖ 评估散列冲突的最重要信息就是负载因子λ，

一般来说：

如果λ较小，散列冲突的几率就小，数据项通常会保存在其所属的散列槽中

如果λ较大，意味着散列表填充较满，冲突会越来越多，冲突解决也越复杂，也就需要更多的比较来找到空槽；如果采用数据链的话，意味着每条链上的数据项增多

❖ 如果采用线性探测的开放定址法来解决冲突（λ在0~1之间）

成功的搜索，平均需要比对次数为：0.5*(1 + 1/(1-λ)) 不成功的搜索，平均比对次数为： 0.5*(1 + 1/(1-λ)^2)

❖ 如果采用数据链来解决冲突（λ可大于1）

成功的搜索，平均需要比对次数为： 1 + λ/2

不成功的搜索，平均比对次数为： λ

排序

================================================================

1.冒泡排序Bubble Sort

---

代码

def bubbleSort(alist):

for passnum in range(len(alist)-1,0,-1):

for i in range(passnum):

if alist[i]>alist[i+1]:

temp = alist[i]

alist[i] = alist[i+1]

alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]

bubbleSort(alist)

print(alist)

结果

[17, 20, 26, 31, 44, 54, 55, 77, 93]

冒泡排序：算法分析

比对次数是1～ n-1的累加：1/2 * n * (n-1)

比对的时间复杂度是O(n^2)

“”"

❖ 关于交换次数，时间复杂度也是O(n^2)，通常每次交换包括3次赋值

❖ 最好的情况是列表在排序前已经有序，交换次数为0

❖ 最差的情况是每次比对都要进行交换，交换次数等于比对次数

❖ 平均情况则是最差情况的一半

❖ 冒泡排序通常作为时间效率较差的排序算法，来作为其它算法的对比基准。

❖ 其效率主要差在每个数据项在找到其最终位置之前，必须要经过多次比对和交换，其中大部分的操作是无效的。

❖ 但有一点优势，就是无需任何额外的存储空间开销。

“”"

性能改进

“”"

❖ 另外，通过监测每趟比对是否发生过交换，可以提前确定排序是否完成

❖ 这也是其它多数排序算法无法做到的

❖ 如果某趟比对没有发生任何交换，说明列表已经排好序，可以提前结束算法"

“”"

def shortBubbleSort(alist):

exchanges = True

passnum = len(alist)-1

while passnum > 0 and exchanges:

exchanges = False

for i in range(passnum):

if alist[i]>alist[i+1]:

exchanges = True

temp = alist[i]

alist[i] = alist[i+1]

alist[i+1] = temp

passnum = passnum - 1

alist=[20,30,40,90,50, 60,70, 80, 100,110]

shortBubbleSort(alist)

print(alist)

结果

[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]

2.选择排序Selection Sort

---

“”"

❖ 选择排序对冒泡排序进行了改进，保留了其基本的多趟比对思路，每趟都使当前最大项就位。

❖ 但选择排序对交换进行了削减，相比起冒泡排序进行多次交换，每趟仅进行1次交换，记录最大项的所在位置，最后再跟本趟最后一项交换

❖ 选择排序的时间复杂度比冒泡排序稍优

比对次数不变，还是O(n2)

交换次数则减少为O(n)

“”"

def selectionSort(alist):

for fillslot in range(len(alist)-1,0,-1):

positionOfMax=0

for location in range(1, fillslot+1):

if alist[location]>alist[positionOfMax]:

positionOfMax = location

temp = alist[fillslot]

alist[fillslot] = alist[positionOfMax]

alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]

selectionSort(alist)

print(alist)

结果

[17, 20, 26, 31, 44, 54, 55, 77, 93]

3.插入排序Insertion Sort

---

“”"

❖ 第1趟，子列表仅包含第1个数据项，将第2个数据项作为“新项” 插入到子列表的合适位置中，这样已排序的子列表就包含了2个数据项

❖ 第2趟，再继续将第3个数据项跟前2个数据项比对，并移动比自身大的数据项，空出位置来，以便加入到子列表中

❖ 经过n-1趟比对和插入，子列表扩展到全表，排序完成

❖ 插入排序的比对主要用来寻找“新项” 的插入位置

❖ 最差情况是每趟都与子列表中所有项进行比对，总比对次数与冒泡排序相同，数量级仍是O(n2)

❖ 最好情况，列表已经排好序的时候，每趟仅需1次比对，总次数是O(n)

“”"

def insertionSort(alist):

for index in range(1,len(alist)):

currentvalue = alist[index] #新项/插入项

position = index

while position>0 and alist[position-1]>currentvalue:

alist[position]=alist[position-1]

position = position-1 # 比对、移动

alist[position]=currentvalue # 插入新项

alist = [54,26,93,17,77,31,44,55,20]

insertionSort(alist)

print(alist)

结果

[17, 20, 26, 31, 44, 54, 55, 77, 93]

4. 谢尔排序Shell Sort

---

• 我们注意到插入排序的比对次数，在最好的情况下是O(n)，这种情况发生在列表已是有序的情况下，实际上， 列表越接近有序，插入排序的比对次数就越少

• 从这个情况入手，谢尔排序以插入排序作为基础，对无序表进行“间隔” 划分子列表，每个子列表都执行插入排序

• 随着子列表的数量越来越少，无序表的整体越来越接近有序，从而减少整体排序的比对次数

• 间隔为3的子列表，子列表分别插入排序后的整体状况更接近有序

• 最后一趟是标准的插入排序，但由于前面几趟已经将列表处理到接近有序，这一趟仅需少数几次移动即可完成

• 子列表的间隔一般从n/2开始，每趟倍增： n/4, n/8…… 直到1

def shellSort(alist):

sublistcount = len(alist)//2 # 间隔设定

while sublistcount > 0:

for startposition in range(sublistcount): # 子列表排序

gapInsertionSort(alist , startposition, sublistcount)

print(“After increments of size” , sublistcount ,“The list is”,alist)

sublistcount = sublistcount // 2 # 间隔缩小

def gapInsertionSort (alist,start,gap):

for i in range(start+gap,len(alist),gap):

currentvalue = alist[i]

position = i

while position>=gap and alist [position-gap]>currentvalue:

alist[position]=alist [position-gap]

position = position-gap

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]

shellSort(alist)

结果

“”"

After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]

After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]

After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]

“”"

• 粗看上去，谢尔排序以插入排序为基础，可能并不会比插入排序好

• 但由于每趟都使得列表更加接近有序，这过程会减少很多原先需要的“无效” 比对

对谢尔排序的详尽分析比较复杂，大致说是介于O(n)和O(n2)之间

• 如果将间隔保持在2k-1(1、 3、 5、 7、 15、 31等等），谢尔排序的时间复杂度约为O（n3/2)

4. 归并排序Merge Sort

---

• 分治策略在排序中的应用

• 归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序

递归的基本结束条件是：数据表仅有1个数据项，自然是排好序的；

缩小规模：将数据表分裂为相等的两半，规模减为原来的二分之一；

调用自身：将两半分别调用自身排序，然后将分别排好序的两半进行

def mergeSort(alist):

if len(alist)>1:# 基本结束条件

mid = len(alist)//2

lefthalf = alist[ :mid]

righthalf = alist[mid:]

mergeSort(lefthalf) # 递归调用

mergeSort(righthalf)

i=j=k=0

while i<len(lefthalf) and j<len(righthalf):#拉链式交错把左右半部从小到大归并到结果列表中

if lefthalf[i]<righthalf[j]:

alist[k]=lefthalf[i]

i=i+1

else:

alist[k]=righthalf[j]

j=j+1

k=k+1

while i<len(lefthalf):#归并左半部剩余项

alist[k]=lefthalf[i]

i=i+1

k=k+1

while j<len(righthalf):#归并右半部剩余项

alist[k]=righthalf[j]

j=j+1

k=k+1

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

结果

[17, 20, 26, 31, 44, 54, 55, 77, 93]

另一个归并排序代码

def merge_sort(lst):

#递归结束条件

if len(lst) <= 1:

return lst

#分解问题，并递归调用

middle = len(lst) // 2

left = merge_sort(lst[:middle]) #左半部排好序

right = merge_sort(lst[middle:]) # 右半部排好序

#合并左右半部，完成排序

merged = []

while left and right :

if left[0] <= right[0]:

merged. append(left.pop(0))

else:

merged. append(right . pop(0))

merged.extend(right if right else left)

return merged

alist = [54,26,93,17,77,31,44,55,20]

print(merge_sort(alist))

结果

[17, 20, 26, 31, 44, 54, 55, 77, 93]

• 归并排序：算法分析

❖ 将归并排序分为两个过程来分析： 分裂和归并

❖ 分裂的过程，借鉴二分搜索中的分析结果，是对数复杂度，时间复杂度为O(log n)

❖ 归并的过程，相对于分裂的每个部分，其所有数据项都会被比较和放置一次，所以是线性复杂度，其时间复杂度是O(n)

综合考虑，每次分裂的部分都进行一次O(n)的数据项归并，总的时间复杂度是O(nlog n)

❖ 最后，我们还是注意到两个切片操作为了时间复杂度分析精确起见，可以通过取消切片操作，

改为传递两个分裂部分的起始点和终止点，也是没问题的，只是算法可读性稍微牺牲一点点。

❖ 我们注意到归并排序算法使用了额外1倍的存储空间用于归并 ,这个特性在对特大数据集进行排序的时候要考虑进去

5.快速排序Quick Sort

---

• 快速排序的思路是依据一个“中值” 数据项来把数据表分为两半：小于中值的一半和大于中值的一半，然后每部分分别进行快速排序（递归）

如果希望这两半拥有相等数量的数据项，则应该找到数据表的“ 中位数”

但找中位数需要计算开销！要想没有开销，只能随意找一个数来充当“ 中值”

比如，第1个数。

• 快速排序的递归算法“递归三要素”

❖ 基本结束条件：数据表仅有1个数据项，自然是排好序的

❖ 缩小规模：根据“中值” ，将数据表分为两半，最好情况是相等规模的两半

❖ 调用自身：将两半分别调用自身进行排序

（排序基本操作在分裂过程中）

• 代码

“”"

❖ 分裂数据表的目标：找到“中值” 的位置

❖ 分裂数据表的手段

设置左右标（left/rightmark）

左标向右移动，右标向左移动

• 左标一直向右移动，碰到比中值大的就停止

• 右标一直向左移动，碰到比中值小的就停止

• 然后把左右标所指的数据项交换

继续移动，直到左标移到右标的右侧，停止移动

这时右标所指位置就是“ 中值” 应处的位置

将中值和这个位置交换

分裂完成，左半部比中值小，右半部比中值大

“”"

def quickSort(alist):

quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist, first,last):

if first<last: #基本结束条件

splitpoint = partition(alist, first,last)# 分裂

quickSortHelper(alist , first , splitpoint-1)#递归调用

quickSortHelper( alist , splitpoint+1,last)

def partition(alist, first, last):

pivotvalue = alist[first] #选定“中值"

leftmark = first + 1 #左右标初值

rightmark = last

done = False

while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvalue:

leftmark = leftmark + 1 #向右移动左标

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:

rightmark = rightmark - 1 #向左移动右标

if rightmark < leftmark: #两标相错就结束移动

done = True

else: #左右标的值交换

temp = alist[leftmark]

alist[leftmark] = alist[rightmark]

alist[rightmark] = temp

temp = alist[first] #中值就位

alist[first] = alist[rightmark]

alist[rightmark] = temp

return rightmark # 中值点，也是分裂点

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]

quickSort(alist)

print(alist)

结果

[17, 20, 26, 31, 44, 54, 55, 77, 93]

• 快速排序：算法分析

❖ 快速排序过程分为两部分： 分裂和移动

如果分裂总能把数据表分为相等的两部分，那么就是O(logn)的复杂度；

而移动需要将每项都与中值进行比对，还是O(n)

❖ 综合起来就是O(nlog n)；

❖ 而且，算法运行过程中不需要额外的存储空间。

❖ 但是，如果不那么幸运的话，中值所在的分裂点过于偏离中部，造成左右两部分数量不平衡

❖ 极端情况，有一部分始终没有数据，这样时间复杂度就退化到O(n2)

还要加上递归调用的开销（比冒泡排序还糟糕）

❖ 可以适当改进下中值的选取方法，让中值更具有代表性

比如“ 三点取样” ，从数据表的头、尾、中间选出中值

会产生额外计算开销，仍然不能排除极端情况

算法复杂度总结

=====================================================================

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Python工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Python开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Python开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024c （备注Python）

一、Python所有方向的学习路线

Python所有方向路线就是把Python常用的技术点做整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照上面的知识点去找对应的学习资源，保证自己学得较为全面。

二、学习软件

工欲善其事必先利其器。学习Python常用的开发软件都在这里了，给大家节省了很多时间。

三、入门学习视频

我们在看视频学习的时候，不能光动眼动脑不动手，比较科学的学习方法是在理解之后运用它们，这时候练手项目就很适合了。

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！

47b8a67243c1008edf79.png)

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Python开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024c （备注Python）
[外链图片转存中…(img-8CGP3nFa-1712707252340)]

一、Python所有方向的学习路线

Python所有方向路线就是把Python常用的技术点做整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照上面的知识点去找对应的学习资源，保证自己学得较为全面。

二、学习软件

工欲善其事必先利其器。学习Python常用的开发软件都在这里了，给大家节省了很多时间。

三、入门学习视频

我们在看视频学习的时候，不能光动眼动脑不动手，比较科学的学习方法是在理解之后运用它们，这时候练手项目就很适合了。

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
[外链图片转存中…(img-seOBt00Z-1712707252340)]