那些高频的Python基础面试题

本文背景：

笔者作为质量保证团队的leader，在面试过程中发现了一些有趣的现象，比如：

简历上写了解，其实是知道有这么个名词存在而已；

简历上写熟悉，其实是搭建过相关环境而已；

简历上写精通，其实是写了个Demo而已(官方文档提供的API估计都没看全)。

受以上因素影响，个人感受比较深的是对有招聘需求的团队来说面试质量低下，招人成本比较高，对面试者来说，面试过程也比较痛苦。

基于此，特总结了下Python相关的面试题，以期有机缘读到此文的小伙伴扎好基础，打牢基本功。

一：Python语言特性

1.1 Python中内置的数据类型，可变类型和不可变类型分别有哪些？

Python中内置的数据类型有一下几种：

Boolean【布尔型】
Number【数值型】(可以是整数，浮点数，分数，复数)
String【字符串型】
Byte【字节】
List【列表】
Tuple 【元组】
Set 【集合】
Dictionary 【字典】

其中不可变的3种类型是：Number(数值)，String(字符串)，Tuple(元组)_

可变的3种类型是：List(列表)，Dictionary(字典)，Set(集合)。

1.2 Python中pass语句的作用是什么？

pass语句什么都不会做。
在编写代码时，为了保证语法的格式和语义的完整性，可使用pass语句。

1.3 请描述下Python中变量的作用域。

Python中变量的作用域有4中：

L(Local)：局部作用域
E(Enclosing) 闭包函数之外的函数中
G(Global) 全局作用域
B(Built-in) 内建作用域

Python 的变量名解析机制也称为 LEGB 法则。就是说在Python中变量解析以L->E->G-B的规则查找，也即：在局部中找不到，便会到局部外的局部找(如：闭包)，找不到再到全局找，最后在内置中找。

1.4 Python中如何实现在函数中设置一个全局变量？

使用global关键字进行声明即可。

1.5 Python中global和globals的区别？

global关键字用来定义一个变量为全局变量。
globals方法返回一个dict对象，dict的键是对象名称，dict的值是对象值。

1.6 Python中单引号，双引号，三引号的区别是什么？

Python中单引号，双引号和三引号都可以用来包含字符串。
三引号包含的字符串可以由多行组成，一般表示打断的描述性字符串。
双引号和三引号都可以包含单引号，三引号可以包含双引号，并且不需要转义。

1.7 Python中list, tuple, dict,set的区别和使用场景是什么？

List(列表)：
1：list使用方括号[]包括起来的有序元素集合。
2：可以使用下标索引来访问list。
Tuple(元组)：
1：元组将多样的对象集合到一起，不能修改，通过下标索引进行查找。使用()小括号包括。
2：可以将tuple看做是不可变的list。
Dict(字典)：
1：字典是一组键(key)值(value)对的组合，通过键(key)进行查找，没有顺序，私用大括号{}包括。
Set(集合)：
1：集合是无需的，元素只出现一次。自动去重。
2：set和dict的唯一区别仅在于没有存储对应的value。

使用场景：

List：简单的数据集合,可以使用索引;

Tuple：把一些数据当做一个整体去使用,不能修改;

Dict：使用键值和值进行关联的数据;

Set：数据只出现一次,只关心数据是否出现, 不关心其位置。

1.8 Python中is和==的区别是什么？

Python中一切皆对象，而Python中的对象包含3个基本元素，分别是：id(身份标识)， type(数据类型)和value(值)。对象之间的比较可以使用==，也可以用is。

is 比较的是两个对象的id值是否相等，也就是比较两个对象是否为同一个实例对象，是否指向同一个内存地址。
== 比较的是两个对象的内容是否相等，默认调用对象的__eq__()方法。

1.9 Python中*args和**kwargs的区别是什么？

*args 和 **kwargs 是Python对不定长参数的处理机制。

*args 表示任何多个无名参数，它本质是一个tuple；
**kwargs 表示任意多个关键字参数，它本质上是一个dict。

两者同时使用时,*args在前,**kwargs在后面,也就是带等号的(字典格式)形参实参传入要放在后面

1.10 Python中range和xrange的区别是什么？

Python2中：

range返回一个list对象，xrange返回一个生成器。

需要生成很大的数字序列的时，用xrange性能会优很多，因为不需要一开始就开辟一块很大的内存空间。

Python3中：

Python3中去掉了xrange这个方法并且将原先xrange的实现方式改为xrange的方式。

1.11 请谈谈对Python中迭代器和生成器的理解。

容器(container)

容器是一种把多个元素组织在一起的数据结构，容器中的元素可以逐个地迭代获取，可以用in, not in关键字判断元素是否包含在容器中。通常这类数据结构把所有的元素存储在内存中（也有一些特例，并不是所有的元素都放在内存，比如迭代器和生成器对象）在Python中，常见的容器对象有：

 list, deque, ....
 
 set, frozensets, ....
 
 dict, defaultdict, OrderedDict, Counter, ....
 
 tuple, namedtuple, …
 
 str
 

可迭代对象(iterable)

很多容器都是可迭代对象，此外还有更多的对象同样也是可迭代对象，比如处于打开状态的files，sockets等等。凡是可以返回一个迭代器的对象都可称之为可迭代对象。

迭代器(iterator)

任何实现了__iter__和__next__next()方法的对象都是迭代器。

__iter__返回迭代器自身，__next__返回容器的下一个值(若容器中无更多元素，则抛出stopiteration异常)。

迭代器就像一个懒加载的工厂，等到有人需要的时候才给它生成值返回，没调用的时候就处于休眠状态等待下一次调用。

生成器(generator)

生成器一定是迭代器，它是一种特殊的迭代器。

生成器不需要实现__iter__和__next__方法，只需要一个yiled关键字。

生成器表达式(grnerator expression)

生成器表达式是列表推倒式的生成器版本，看起来像列表推导式，但是它返回的是一个生成器对象而不是列表对象。

1.12 Python中type和instance的区别？

type和isinstance都可以判断变量是否属于某个内建类型。
type只接收一个参数，不但可以判断变量是否属于某个类型，而且可以得到参数变量未知的所属的类型；
而isinstance只能判断是否属于某个已知类型，不能直接得到变量未知的所属的类型。
isinstance可以判断子类实例对象是属于父类的；而type会判断子类实例对象和父类类型不一样。

1.13 请聊聊Python中常用的字符串操作。

字符串包含(in, not in)

字符串长度(len)

字符串切片(split)

字符串查找(find)

字符串小写(lowercase)

字符串大写(upper)

大小写互换(swapcase)

字符串连接(join)

字符串截取[:-3]

1.14 描述下您对Python中单下划线和双下划线的理解。

使用单下划线(_)开头表示方法不是API的一部分，不建议直接访问。
使用双下划线(__)开头表示子类不能覆盖该方法。
有些属性只在末尾加了单下划线(_)，仅仅是为了避免名称和Python关键字的冲突。

1.15 Python中类方法，成员方法和静态方法有何区别？

成员方法只能被实例对象调用；
静态方法(由@staticmethoc装饰)和类方法(由@classmethod装饰)可以被类或类的实例对象调用。
成员方法：第一个参数必须要默认传实例对象，用self表示。
静态方法：参数没有要求。
类方法：第一个参数必须要默认传类，用cls表示。

1.16 谈谈对Python自省机制的理解。

自省是通过一定的机制查询到对象的内部结构能做什么。

Python中提供了很多的方法来查询对象的内部结构，比如：
 hasattr:查询对象是否有一个特性的属性
 getattr:获取对象的属性
 setattr:设置对象的属性
 delattr:从一个对象中删除属性

1.17 谈谈对Python中异常处理的理解。

Python中的异常：

在Python当中，若一个程序在运行的时候出错，Python解释器会自动的在出错的地方生成一个异常对象，而后Python解释器会自动的在出错地方的附近寻找有没有对这个异常对象处理的代码，Python解释器会简单粗暴地终止程序运行并输出错误信息。

Python中的异常处理：

1：默认的异常处理
中断程序运行，在终端输出异常信息。
2：try...except
except后可跟具体异常，也可为空(表示捕获任何类型的异常)。
except将异常处理完毕后将继续后续的执行。
3：try...finally
finally表示无论异常是否发生，finally中的语句都会被执行。
由于没有except处理器，finally执行完毕后便会中断程序。
4：assert
先判断assert后紧跟的语句是True还是False，如果False则调用默认的异常处理器后中断程序。
5：with..as
如果with语句块中发生异常，调用默认的异常处理器。
6：try...raise(自定义异常并主动抛出)

1.18 谈谈对Python装饰器的理解。

装饰器：装饰器本质上是一个Python函数，它可以让其他函数在不需要做任何代码变动的前提下增加额外功能，装饰器的返回值也是一个函数对象。

它经常用于有切面需求的场景，比如：插入日志、性能测试、事务处理、缓存、权限校验等场景。装饰器是解决这类问题的绝佳设计，有了装饰器，我们就可以抽离出大量与函数功能本身无关的雷同代码并继续重用。

1.19 谈谈对Python新式类和经典类的理解

Pyton2中默认都是经典类(只有显示继承了object才是新式类)，

Python3中默认都是新式类。

在多继承中，新式类采用广度优先搜索，而旧式类是采用深度优先搜索。

新式类相同父类只执行一次构造函数，经典类重复执行多次。

1.20 Python的魔法方法是什么？__new__和__init__的区别是什么？

Python中的魔法方法是指可以给我们的类增加魔力的特殊方法。如果对象实现(重载)了这些方法中的某一个，那么这个方法就会在特殊的情况下被调用。它们经常是双下划线包围来命名的(比如:__init__)。

__new__：用来创建一个雷的实例(constructor)。
__init__：用来初始化一个实例(initializer)。
__new__：接收的第一个参数是cls。
__init__：接收的第一个参数是self。
__init__是在__new__之后被调用的。
__init__不能有返回值。__new__可以直接返回其他类的实例。

1.21 描述对Python全局锁GIL的理解。

GIL全局解释器锁并不是Python语言的特性，它是在现实Python解释器时引用的一个概念。GIL只在CPython解释器上存在。

GIL作用：保证同一时间内只有一个线程在执行。

GIL影响：

1.Python中同一时刻有且只有一个线程会执行；

2.Python中的多个线程由于GIL锁的存在无法利用多核CPU；

3.Python中的多线程不适合计算机密集型的程序；

4.如果程序需要大量的计算，利用多核CPU资源，可以使用多进程来解决。

GIL解决：

1.更换更高版本的解释器，比如3.6，从3.2版本开始，据说Python对解释做了优化

2.更换解释器，比如JPython，但是由于比较小众，支持的模块较少，导致开发的效率降低

3.Python为了解决程序使用多核的问题，使用多进程代替多线程

1.22 对Python中进程，线程，协程的理解。

进程

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动（运行的程序或者代码）,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。由于进程比较重量，占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大，但相对比较稳定安全。

线程

线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。线程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。

协程

协程又称微线程,是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

线程与进程的区别：

同一个进程中的线程共享同一内存空间，但是进程之间是独立的。

同一个进程中的所有线程的数据是共享的（进程通讯），进程之间的数据是独立的。

对主线程的修改可能会影响其他线程的行为，但是父进程的修改（除了删除以外）不会影响其他子进程。

一个进程至少有一个进程

同一个进程的线程之间可以直接通信，但是进程之间的交流需要借助中间代理来实现。

创建新的线程很容易，但是创建新的进程需要对父进程做一次复制。

一个线程可以操作同一进程的其他线程，但是进程只能操作其子进程。

线程启动速度快，进程启动速度慢（但是两者运行速度没有可比性）

线程与协程的区别：

一个线程可以多个协程，一个进程也可以单独拥有多个协程，这样python中则能使用多核CPU。

线程进程都是同步机制，而协程则是异步

协程能保留上一次调用时的状态，每次过程重入时，就相当于进入上一次调用的状态

1.23 谈谈对Python垃圾回收机制的理解。

python采用的是引用计数机制为主，标记-清除和分代收集两种机制为辅的策略

引用计数：

一种垃圾收集机制，而且也是一种最直观，最简单的垃圾收集技术, 当一个对象的引 用被创建或者复制时，对象的引用计数加 1；当一个对象的引用被销毁时，对象的引用计数减 1；当对 象的引用计数减少为 0 时，就意味着对象已经没有被任何人使用了，可以将其所占用的内存释放了。虽 然引用计数必须在每次分配和释放内存的时候加入管理引用计数的动作，然而与其他主流的垃圾收集技 术相比，引用计数有一个最大的有点，即“实时性”，任何内存，一旦没有指向它的引用，就会立即被 回收。而其他的垃圾收集计数必须在某种特殊条件下（比如内存分配失败）才能进行无效内存的回收。

引用计数机制执行效率问题：引用计数机制所带来的维护引用计数的额外操作与 Python 运行中所 进行的内存分配和释放，引用赋值的次数是成正比的。而这点相比其他主流的垃圾回收机制，比如“标 记-清除”，“停止-复制”，是一个弱点，因为这些技术所带来的额外操作基本上只是与待回收的内存 数量有关。

如果说执行效率还仅仅是引用计数机制的一个软肋的话，那么很不幸，引用计数机制还存在着一个 致命的弱点，正是由于这个弱点，使得侠义的垃圾收集从来没有将引用计数包含在内，能引发出这个致 命的弱点就是循环引用（也称交叉引用）。 问题说明：

循环引用可以使一组对象的引用计数不为 0，然而这些对象实际上并没有被任何外部对象所引用， 它们之间只是相互引用。这意味着不会再有人使用这组对象，应该回收这组对象所占用的内存空间，然 后由于相互引用的存在，每一个对象的引用计数都不为 0，因此这些对象所占用的内存永远不会被释放。 比如：这一点是致命的，这与手动进行内存管理所产生的内存泄露毫无区别。

要解决这个问题，Python 引入了其他的垃圾收集机制来弥补引用计数的缺陷：“标记-清除”，

标记-清除：

标记-清除”是为了解决循环引用的问题。可以包含其他对象引用的容器对象（比如：list，set，dict，class，instance）都可能产生循环引用。

我们必须承认一个事实，如果两个对象的引用计数都为 1，但是仅仅存在他们之间的循环引用，那么这两个对象都是需要被回收的，也就是说，它们的引用计数虽然表现为非 0，但实际上有效的引用计数为 0。我们必须先将循环引用摘掉，那么这两个对象的有效计数就现身了。假设两个对象为 A、B，我们从 A 出发，因为它有一个对 B 的引用，则将 B 的引用计数减 1；然后顺着引用达到 B，因为 B 有一个对 A 的引用，同样将 A 的引用减 1，这样，就完成了循环引用对象间环摘除。

但是这样就有一个问题，假设对象 A 有一个对象引用 C，而 C 没有引用 A，如果将 C 计数引用减 1，而最后 A 并没有被回收，显然，我们错误的将 C 的引用计数减 1，这将导致在未来的某个时刻出现一个对 C 的悬空引用。这就要求我们必须在 A 没有被删除的情况下复原 C 的引用计数，如果采用这样的方案，那么维护引用计数的复杂度将成倍增加。

原理：“标记-清除”采用了更好的做法，我们并不改动真实的引用计数，而是将集合中对象的引用计数复制一份副本，改动该对象引用的副本。对于副本做任何的改动，都不会影响到对象生命走起的维护。这个计数副本的唯一作用是寻找 root object 集合（该集合中的对象是不能被回收的）。当成功寻找到 root object 集合之后，首先将现在的内存链表一分为二，一条链表中维护 root object 集合，成为 root 链表，而另外一条链表中维护剩下的对象，成为 unreachable 链表。之所以要剖成两个链表，是基于这样的一种考虑：现在的 unreachable 可能存在被 root 链表中的对象，直接或间接引用的对象，这些对象是不能被回收的，一旦在标记的过程中，发现这样的对象，就将其从 unreachable 链表中移到root 链表中；当完成标记后，unreachable 链表中剩下的所有对象就是名副其实的垃圾对象了，接下来的垃圾回收只需限制在 unreachable 链表中即可。

分代回收

背景：分代的垃圾收集技术是在上个世纪 80 年代初发展起来的一种垃圾收集机制，一系列的研究表明：无论使用何种语言开发，无论开发的是何种类型，何种规模的程序，都存在这样一点相同之处。即：一定比例的内存块的生存周期都比较短，通常是几百万条机器指令的时间，而剩下的内存块，起生存周期比较长，甚至会从程序开始一直持续到程序结束。

从前面“标记-清除”这样的垃圾收集机制来看，这种垃圾收集机制所带来的额外操作实际上与系统中总的内存块的数量是相关的，当需要回收的内存块越多时，垃圾检测带来的额外操作就越多，而垃圾回收带来的额外操作就越少；反之，当需回收的内存块越少时，垃圾检测就将比垃圾回收带来更少的额外操作。为了提高垃圾收集的效率，采用“空间换时间的策略”。

原理：将系统中的所有内存块根据其存活时间划分为不同的集合，每一个集合就成为一个“代”，垃圾收集的频率随着“代”的存活时间的增大而减小。也就是说，活得越长的对象，就越不可能是垃圾，就应该减少对它的垃圾收集频率。那么如何来衡量这个存活时间：通常是利用几次垃圾收集动作来衡量，

如果一个对象经过的垃圾收集次数越多，可以得出：该对象存活时间就越长。

1.24 Python中赋值，深拷贝和浅拷贝的区别？

赋值（=）
就是创建了对象的一个新的引用，修改其中任意一个变量都会影响到另一个。
浅拷贝
创建一个新的对象，但它包含的是对原始对象中包含项的引用（如果用引用的方式修改 其中一个对象，另外一个也会修改改变）{1,完全切片方法；2，工厂函数，如 list()；3，copy 模块 的 copy()函数}。
深拷贝
创建一个新的对象，并且递归的复制它所包含的对象（修改其中一个，另外一个不会改 变）{copy 模块的 copy.deepcopy()函数}。

二：10大经典排序算法实现

2.1 排序算法总结

IMG_256

2.2 冒泡排序

算法步骤：

1：比较相邻的两个元素，如果第二个比第一个小，就进行两者位置交换。

2：对每一对相邻的元素作比较，知道无任何一对元素需要比较。

算法实现：

# -*- coding = utf-8 -*-
 
 source_list = [1, 3, 2, 6, 8, 56, 18, 99]
 
 
 def bubble_sort(list_data):
 for index in range(1, len(list_data)):
 for element in range(0, len(list_data)-1):
 if list_data[element] > list_data[element+1]:
 list_data[element], list_data[element+1] = list_data[element+1], list_data[element]
 return list_data
 
 
 sort_result = bubble_sort(source_list)
 
 print(sort_result)

2.3 插入排序

算法步骤：

1：将第一个元素作为一个有序序列，其他所有元素作为未排序序列。

2：遍历所有元素，将查找到的每个元素插入到有序序列的适当位置。

算法实现：

def insert_sort(list_data):
 for index in range(1, len(list_data)):
 pre_index = index-1
 current_element = list_data[index]
 while pre_index >= 0 and list_data[pre_index] > current_element:
 list_data[pre_index + 1] = list_data[pre_index]
 pre_index -= 1
 list_data[pre_index + 1] = current_element
 return list_data
 
 
 sort_result = insert_sort(source_list)
 print(sort_result)

2.4 选择排序

算法步骤：

1：在未排序序列中找到最大(小)元素，放在序列的起始位置。

2：从剩余未排序序列中继续寻找最大(小)元素，存在已排序序列的末尾。

3：重复步骤2，知道所有的元素均已排序。

算法实现：

def select_sort(list_data):
 for index in range(0, len(list_data)-1):
 max_index = index
 for element in range(index+1, len(list_data)):
 if list_data[element] > list_data[max_index]:
 max_index = element
 if index != max_index:
 list_data[index], list_data[max_index] = list_data[max_index], list_data[index]
 return list_data
 
 
 sort_result = select_sort(source_list)
 print(sort_result)

2.5 快速排序

算法步骤：

1：从待排序序列中选择一个元素作为参照物。

2：遍历待排序序列，比参照物值小的拍在前面，值大的排在后面。

3：对每个元素递归排序。

算法实现：

def quick_sort(list_data, left_index, right_index):
 if left_index >= right_index:
 return
 stack = []
 stack.append(left_index)
 stack.append(right_index)
 while stack:
 low = stack.pop(0)
 high = stack.pop(0)
 if high - low <= 0:
 continue
 x = list_data[high]
 i = low - 1
 for j in range(low, high):
 if list_data[j] <= x:
 i += 1
 list_data[i], list_data[j] = list_data[j], list_data[i]
 list_data[i + 1], list_data[high] = list_data[high], list_data[i + 1]
 stack.extend([low, i, i + 2, high])
 print(list_data)
 
 
 quick_sort(source_list, 0, 7)

2.6 希尔排序

算法步骤：

1：选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2：按增量序列个数 k，对序列进行 k 趟排序；

3：每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法实现：

def shell_sort(list_data):
 start = 1
 while start < len(list_data)/3:
 start = start*3 + 1
 while start > 0:
 for index in range(start, len(list_data)):
 temp_element = list_data[index]
 next_count = index - start
 while next_count >=0 and list_data[next_count] > temp_element:
 list_data[next_count+start] = list_data[next_count]
 next_count -= start
 start = math.floor(start/3)
 return list_data
 
 
 sort_result = shell_sort(source_list)
 print(sort_result)

2.7 归并排序

算法步骤：

1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

3 合并：将各个子问题的解合并为原问题的解。

算法实现：

def merge_sort(seq):
"""归并排序"""
if len(seq) <= 1:
return seq
mid = len(seq) / 2 # 将列表分成更小的两个列表
# 分别对左右两个列表进行处理，分别返回两个排序好的列表
left = mergesort(seq[:mid])
right = mergesort(seq[mid:])
# 对排序好的两个列表合并，产生一个新的排序好的列表
return merge(left, right)
def merge(left, right):
"""合并两个已排序好的列表，产生一个新的已排序好的列表"""
result = [] # 新的已排序好的列表
i = 0 # 下标
j = 0
# 对两个列表中的元素 两两对比。
# 将最小的元素，放到result中，并对当前列表下标加1
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result

2.8 堆排序

算法步骤：

1 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。

2 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。

3 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点

算法实现：

def heap_sort(ary) :
n = len(ary)
#最后一个非叶子节点
first = int(n/2-1)
#构造大根堆
for start in range(first,-1,-1) :
max_heapify(ary,start,n-1)
#堆排，将大根堆转换成有序数组
for end in range(n-1,0,-1):
ary[end],ary[0] = ary[0],ary[end]
max_heapify(ary,0,end-1)
return ary
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
root = start
while True :
#调整节点的子节点
child = root*2 +1
if child > end : break
if child+1 <= end and ary[child] < ary[child+1] :
#取较大的子节点
child = child+1
#较大的子节点成为父节点
if ary[root] < ary[child] :
#交换
ary[root],ary[child] = ary[child],ary[root]
root = child
else :
break

2.9 计数排序

算法原理：

找到给定序列的最小值与最大值 创建一个长度为最大值-最小值+1的数组，初始化都为0 然后遍历原序列，并为数组中索引为当前值－最小值的值＋１ 此时数组中已经记录好每个值的数量，自然也就是有序的了

算法实现：

def count_sort(list_data, max_value):
 bucket_len = max_value+1
 bucket = [0]*bucket_len
 sorted_index =0
 arr_len = len(list_data)
 for i in range(arr_len):
 if not bucket[list_data[i]]:
 bucket[list_data[i]]=0
 bucket[list_data[i]]+=1
 for j in range(bucket_len):
 while bucket[j]>0:
 list_data[sorted_index] = j
 sorted_index+=1
 bucket[j]-=1
 return list_data
 
 
 sort_result = count_sort(source_list, 99)
 print(sort_result)

2.10 桶排序

算法原理：

设待排序序列的元素取值范围为0到m，则我们新建一个大小为m+1的临时数组并把初始值都设为0，遍历待排序序列，把待排序序列中元素的值作为临时数组的下标，找出临时数组中对应该下标的元素使之+1；然后遍历临时数组，把临时数组中元素大于0的下标作为值按次序依次填入待排序数组，元素的值作为重复填入该下标的次数，遍历完成则排序结束序列有序。

算法实现：

def bucket_sort(list_data):
 buckets = [0] * ((max(list_data) - min(list_data))+1)
 for i in range(len(list_data)):
 buckets[list_data[i]-min(list_data)] += 1
 sort_result=[]
 for i in range(len(buckets)):
 if buckets[i] != 0:
 sort_result += [i+min(list_data)]*buckets[i]
 return sort_result
 
 
 sort_result = bucket_sort(source_list)
 print(sort_result)

2.11 基数排序

算法原理：

将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。

算法实现：

def radix_sort(list_data, d=3):
 for i in range(d):
 s = [[] for k in range(10)]
 for j in list_data:
 s[int(j / (10 ** i)) % 10].append(j)
 sort_result = [a for b in s for a in b]
 print(sort_result)
 
 
 radix_sort(source_list)

三：文末彩蛋

本文只是仅仅对Python基础知识的部分做了些总结，如果小伙伴们有心，可以从下面几个领域继续积累总结

1：数据结果(树，堆，栈)

2：Python的Web开发(Django，Flask)

3：网络协议

4：设计模式

加油！小伙伴们~~~

我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表