数据类型篇 本篇的练习题旨在考察你对基本数据类型的理解熟悉程度，适合刚接触python的初学者用来巩固对基础知识的理解
基本数据类型 逻辑推理练习（类型转换） 不运行程序，说出下面程序的执行结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1. 4.0 == 4 2. "4.0" == 4 3. bool("1") 4. bool("0") 5. str(32) 6. int(6.26) 7. float(32) 8. float("3.21") 9. int("434") 10. int("3.42") 11. bool(-1) 12. bool("") 13. bool(0) 14. "wrqq" > "acd" 15. "ttt" == "ttt " 16. "sd"*3 17. "wer" + "2322"
答案如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1. True 2. False 3. True 4. True 5. '32' 6. 6 7. 32.0 8. 3.21 9. 434 10. 会报错 11. True 12. False 13. False 14. True 15. False 16. "sdsdsd" 17. 'wer2322'
关于这些答案，要做到知其然且知其所以然，编程需要精准的知道每一个细节，下面对其中一些可能让你感到困惑的知识点进行讲解
bool函数转换规则 bool函数进行转换时，其结果取决于传入参数与True和False的等价关系，只需记住一点即可
0 , 空字符串, None在条件判断语句中等价于False, 其他数值都等价于True
bool函数在做数据类型转换时遵循该原则
int(“3.42”) 为什么会报错 字符串”3.42”可以转成float类型数据3.42, 3.42可以转成int类型数据3，但是字符串”3.42”却不可以直接使用int函数转成3，讲实话，我也觉得这个函数有些不灵活，或许是语言的发明者有自己的考虑吧，咱们对这种问题，不必深究，先做到知道它是什么，将来再去研究为什么
字符串大小比较规则 两个字符串在比较大小时，比的不是长度，而是内容
字符串左对齐后，逐个字符依次比较，直到可以分出胜负
“sd”*3 “sd”*3 的意思是sd重复3次，生成一个新的字符串
数据类型考察 请说出下面表达式结果的类型
1 2 3 4 5 6 1. "True" 2. "Flase" 3. 4 >= 5 4. 5 5. 5.0 6. True
非常简单的送分题
1 2 3 4 5 6 1. str 2. str 3. bool 4. int 5. float 6. bool
唯一需要解释的是4 >= 5,4比5小，怎么可能大于等于5呢，这是错误的，既然是错的，那么就等于False,False的类型是bool
交互式解释器练习 请在交互式解释器里回答下面的题目
1 2 3 4 5 1. 3的5次方 2. 7对2求模 3. 9除5，要求有小数部分 4. 9除5，要求没有小数部分 5. 用程序计算根号16，也就是16的2分之一次方
答案如下
1 2 3 4 5 6 1. 3**5 2. 7%2 3. 9/5 4. 9//5 5. import math math.sqrt(16)
知识点讲解 幂运算用两个， 2的2次方表示为2* 2 求模运算用%， 其实就是求余数，不知道余数的打电话给小学老师 除法中，希望结果有小数部分时用/， 希望只保留整数部分时用 // ,没啥可解释的，请记住他们的区别，懒得记，就别学编程，编程不适合懒惰的人 开根号，要用到math模块的sqrt方法，这个题目需要你自己去百度或是谷歌，第一次明确的建议你，一定要好好利用搜索引擎，不会用搜索引擎的程序员，永远是菜鸟 逻辑推理练习（字符串） 不用代码，口述回答下面代码的执行结果
string[1:20] string[20] string[3:-4] string[-10:-3] string.lower() string.replace(“o”, “0”) string.startswith(‘python’) string.split() len(string) string[30] string.replace(“ “, ‘’) 答案如下
1 2 3 4 5 6 7 8 9 10 11 1. 'ython is good' 2. 报错 3. 'hon is ' 4. 'on is g' 5. 'python is good' 6. 'Pyth0n is g00d' 7. False 8. ['Python', 'is', 'good'] 9. 14 10. 报错 11. 'Pythonisgood'
第2题和第10题都报错，是因为超出了索引范围，字符串长度为14，你去20和30的位置取值，当然会报错
关于切片操作，只需要知道从哪里开始到哪里结束就一定能推导出答案，以string[3:-4]为例，3是开始的位置，-4是结束的位置，但这个范围是左闭右开的，从3开始没错，但不会到-4，而是到-5，更前面的一个位置，python支持负数索引，或者说是反向索引，从右向左从-1开始逐渐减小。
第一题中，做切片的时候是从1开始，到20结束，即便是右开，直到19，也仍然超出了索引范围，为什么不报错呢，这就是语言设计者自己的想法了，切片时，不论是开始位置还是结束位置，超出索引范围都不会报错，我猜，大概是由于切片是一个范围操作，这个范围内有值就切出来，没值返回空字符串就好了。
列表与元组练习题 列表基础考察 已知一个列表
求列表的长度 判断6 是否在列表中 lst + [6, 7, 8] 的结果是什么？ lst*2 的结果是什么 列表里元素的最大值是多少 列表里元素的最小值是多少 列表里所有元素的和是多少 在索引1的后面新增一个的元素10 在列表的末尾新增一个元素20 答案如下
1 2 3 4 5 6 7 8 9 1. len(lst) 2. 6 in lst 3. [1,2,3,4,5,6,7,8] 4. [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] 5. max(lst) 6. min(lst) 7. sum(lst) 8. lst.insert(1, 10) 9. lst.append(20)
以上都是对列表基础操作，所用到的每一个函数，列表的每一个方法，都是需要你熟记于心的
修改列表 lst = [1, [4, 6], True]
答案如下
1 2 3 lst[0] = 2 lst[1][0] = 4 lst[1][1] = 12
你以为存在一个函数，其功能便是将列表里所有的数据都变成原来的两倍，这样才显得变成语言是一个非常神奇的东西，但是很遗憾的告诉你，那些神奇的东西都是程序员自己实现的。
想要修改列表里的数据，必须通过索引对其重新赋值，上面的方法很low，你也可以写一个函数来实现这个功能，我们假设要处理的列表里只int,float,bool,和list数据，不管嵌套基层list，这个函数都应该能正确处理，下面是一段示例代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def double_list (lst ): for index, item in enumerate (lst): if isinstance (item, bool ): continue if isinstance (item, (int , float )): lst[index] *= 2 if isinstance (item, list ): double_list(item) if __name__ == '__main__' : lst = [1 , [4 , 6 ], True ] double_list(lst) print (lst)
元组概念考察 写出下面代码的执行结果和最终结果的类型
(1, 2)*2 (1, )*2 (1)*2 答案如下
1 2 3 1. (1, 2, 1, 2) 2. (1, 1) 3. 2
第一题应该没有异议，关键是第2题和第3题，元组里只有一个数据时，必须有逗号，如果没有逗号，就变成了第3题的形式，第3题本质上是1*2,那对小括号就如同我们小学学过的小括号一样，只是为了体现运算优先级而已。
当元组只有一个数据时，如果不省略了逗号，那么小括号的作用就不再是表示元组，而是表示运算优先级
合并列表 lst = [1,2,3]
答案
这个过程中不会产生新的列表，最直观的检验方式就是print(id(lst)),合并前后，lst的内存地址都没有发生变化，只是列表里的内容发生了变化
合并字符串 str1 = “1,2,3”
答案
这个过程中，产生的新的字符串，字符串是不可变对象，从字面上理解，似乎str1的内容发生变化了，但本质上是产生了新的字符串并赋值给str1， print(str1)， 合并前后的内存地址是不一样的
统计练习 列表lst 内容如下
1 lst = [2 , 5 , 6 , 7 , 8 , 9 , 2 , 9 , 9 ]
请写程序完成下列题目
找出列表里的最大值 找出列表里的最小值 找出列表里最大值的个数 计算列表里所有元素的和 计算列表里元素的平均值 计算列表的长度 找出元素6在列表中的索引 答案
1 2 3 4 5 6 7 1. max(lst) 2. min(lst) 3. lst.count(max(lst)) 4. sum(lst) 5. sum(lst)/float(len(lst)) 6. len(lst) 7. lst.index(6)
这道题考察的是你对内置函数的理解和运用
下面的题目不允许写代码，仅凭思考来回答
lst[2:4] 的值是什么 lst[1: -3]的值是什么 lst[-5]的值是什么 lst[:-4] 的值是什么 lst[-4:] 的值是什么 这个题目主要考察你对列表切片操作的理解
1 2 3 4 5 1. [6, 7] 2. [5, 6, 7, 8, 9] 3. 8 4. [2, 5, 6, 7, 8] 5. [9, 2, 9, 9]
列表的切片操作，最关键的一点在于左闭右开，结束位置的数据不会列入结果中
列表操作练习 列表lst 内容如下
1 lst = [2 , 5 , 6 , 7 , 8 , 9 , 2 , 9 , 9 ]
请写程序完成下列操作
在列表的末尾增加元素15 在列表的中间位置插入元素20 将列表[2, 5, 6]合并到lst中 移除列表中索引为3的元素 翻转列表里的所有元素 对列表里的元素进行排序，从小到大一次，从大到小一次 答案
1 2 3 4 5 6 1. lst.append(15) 2. lst.insert(len(lst)//2, 20) 3. lst.extend([2, 5, 6]) 4. lst.remove(lst[3]) 5. lst = lst[::-1] 6. lst.sort() lst.sort(reverse=True)
复杂列表练习 列表lst 内容如下
1 lst = [1 , 4 , 5 , [1 , 3 , 5 , 6 , [8 , 9 , 10 , 12 ]]]
不写任何代码，仅凭思考来回答下列问题
列表lst的长度是多少 列表lst中有几个元素 lst[1] 的数据类型是什么 lst[3]的数据类型是什么 lst [3] [4] 的值是什么 如果才能访问到 9 这个值 执行lst[3] [4].append([5, 6])后，列表lst的内容是什么，手写出来 lst[-1] [-1] [-2]的值是什么 lst[-2]的值是什么 len(lst[-1]) 的值是什么 len(lst [-1] [-1])的值是什么 lst [-1] [1:3] 的值是什么 lst [-1] [-1] [1:-2]的值是什么 第1题和第2题其实是一个意思，原本统计列表里数据个数不是什么难事，可一旦出现了嵌套列表的情况，有人就分不清了，列表里的数据是以逗号分隔的，lst[3] 是一个列表，其余都是int类型数据，因此lst的长度是4
第3题，lst[1] = 4,是int类型数据
字典练习题 字典基本操作 字典内容如下
1 2 3 4 5 dic = { 'python' : 95 , 'java' : 99 , 'c' : 100 }
用程序解答下面的题目
字典的长度是多少 请修改’java’ 这个key对应的value值为98 删除 c 这个key 增加一个key-value对，key值为 php, value是90 获取所有的key值，存储在列表里 获取所有的value值，存储在列表里 判断 javascript 是否在字典中 获得字典里所有value 的和 获取字典里最大的value 获取字典里最小的value 字典 dic1 = {‘php’: 97}， 将dic1的数据更新到dic中 第1题，len(dic),结果为3
字典应用（买水果） 小明去超市购买水果，账单如下
请将上面的数据存储到字典里，可以根据水果名称查询购买这个水果的费用
很简单哦，用水果名称做key，金额做value，创建一个字典
1 2 3 4 5 info = { '苹果' :32.8 , '香蕉' : 22 , '葡萄' : 15.5 }
字典应用（买水果2） 小明，小刚去超市里购买水果
小明购买了苹果，草莓，香蕉，一共花了89块钱，，小刚购买了葡萄，橘子，樱桃，一共花了87块钱
请从上面的描述中提取数据，存储到字典中，可以根据姓名获取这个人购买的水果种类和总费用。
以姓名做key，value仍然是字典
1 2 3 4 5 6 7 8 9 10 info = { '小明' : { 'fruits' : ['苹果' , '草莓' , '香蕉' ], 'money' : 89 }, '小刚' : { 'fruits' : ['葡萄' , '橘子' , '樱桃' ], 'money' : 87 } }
集合练习题 集合间的运算
1 2 lst1 = [1 , 2 , 3 , 5 , 6 , 3 , 2 ] lst2 = [2 , 5 , 7 , 9 ]
哪些整数既在lst1中，也在lst2中 哪些整数在lst1中，不在lst2中 两个列表一共有哪些整数 虽然题目一直在问两个列表，但用列表解答这3个题目效率很低，你应该用集合
1 2 3 4 5 6 7 8 9 10 11 12 13 14 lst1 = [1 , 2 , 3 , 5 , 6 , 3 , 2 ] lst2 = [2 , 5 , 7 , 9 ] set1 = set (lst1) set2 = set (lst2) print (set1.intersection(set2))print (set1.difference(set2))print (set1.union(set2))
基础语法篇 基础语法篇的练习题，不涉及复杂的逻辑推理，旨在检查你对基础语法的掌握情况
if 条件语句 单个条件分支 使用input函数接收用户的输入，如果用户输入的整数是偶数，则使用print函数输出”你输入的整数是:{value}, 它是偶数”, {value}部分要替换成用户的输入。
完成这个练习题需要你掌握下面4个知识点
input函数的作用 字符串转int 取模运算 字符串格式化 1 2 3 4 value = input ("请输入一个整数:" ) i_value = int (value) if i_value % 2 == 0 : print ("你输入的整数是:{value}, 它是偶数" .format (value=value))
if … else … 使用input函数接收用户的输入，如果用户输入的整数是偶数，则使用print函数输出”你输入的整数是:{value}, 它是偶数”,如果是奇数，则使用print函数输出”你输入的整数是:{value}, 它是奇数”
1 2 3 4 5 6 value = input ("请输入一个整数:" ) i_value = int (value) if i_value % 2 == 0 : print ("你输入的整数是:{value}, 它是偶数" .format (value=value)) else : print ("你输入的整数是:{value}, 它是奇数" .format (value=value))
2.1.3 多条件分支 使用input函数接收用户的输入数据，如果用户输入python，则输出90， 如果用户输入java,输出95，如果用户输入php，输出85，其他输入，程序输出0
1 2 3 4 5 6 7 8 9 10 value = input ("请输入一个整数:" ) if value == 'python' : print (90 ) elif value == 'java' : print (95 ) elif value == 'php' : print (85 ) else : print (0 )
2.1.4 复杂条件判断 使用input函数接收用户的输入，如果输入的数据不可以转换成int类型数据，则输出”无法使用int函数转换”，如果可以，则将用户的输入转成int类型数据并继续判断。
如果输入数据是奇数，则将其乘以2并输出，如果是偶数，则判断是否能被4整除，如果可以则输出被4整除后的值，若不能被4整数，则判断是否大于20，如果大于20则输出与20的差值，如果小于等于20，则直接输出该值
程序代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 value = input ("请输入一个整数:" ) if not value.isdigit(): print ('无法使用int函数转换' ) else : i_value = int (value) if i_value % 2 == 1 : print (i_value*2 ) elif i_value % 4 == 0 : print (i_value / 4 ) elif i_value > 20 : print (i_value - 20 ) else : print (i_value)
for循环 range函数基本使用 1 2 3 4 range (3 , 20 , 4 )range (10 , -3 , -4 )range (10 , 5 )range (2 , 12 )
不使用程序，说出上面4个range产生的整数序列
利用range函数遍历列表 1 2 3 lst = [1 , 3 , 5 , 2 , 7 , 9 ] for index in range (len (lst)): print (lst[index])
参照上面的代码，从后向前遍历 遍历输出列表里的所有偶数 遍历列表，输出大于3的奇数 使用for循环遍历字典 遍历字典有两种方法
1 2 3 4 5 6 7 dic = { 'python' : 90 , 'java' : 95 } for key in dic: print (key, dic[key])
方法2
1 2 3 4 5 6 7 dic = { 'python' : 90 , 'java' : 95 } for key, value in dic.items(): print (key, value)
continue练习 break练习 从列表 lst = [1, 3, 5, 2, 7, 9, 10] 中寻找1个偶数并输出，代码如下
1 2 3 4 5 lst = [1 , 3 , 5 , 2 , 7 , 9 , 10 ] for item in lst: if item % 2 == 0 : print (item) break
题目要求寻找一个偶数，当找到这个偶数后，循环就可以终止了，使用break可以终止本次循环，你可以去掉代码中的break，再次执行代码，观察代码的执行效果
寻找列表中的最大值,最小值 1 2 3 4 5 6 7 8 lst = [3 , 6 , 1 , 8 , 1 , 9 , 2 ] max_value = lst[0 ] for item in lst: if item > max_value: max_value = item print (max_value)
参照上面的代码，写代码寻找列表的最小值 写代码寻找列表里的最小偶数 写代码寻找列表里的最大奇数 寻找组合 1 2 3 4 5 6 7 lst1 = [3 , 6 , 1 , 8 , 1 , 9 , 2 ] lst2 = [3 , 1 , 2 , 6 , 4 , 8 , 7 ] for item1 in lst1: for item2 in lst2: if item1 + item2 == 10 : print ((item1, item2))
上面的代码利用嵌套循环，从两个列表里各取1个数，如果这两个数的和等于10，则以元组的方式输出这两个数
参照上面的代码，寻找两个数的差的绝对值等于2的组合 两个列表里各取出一个值，item1和item2， 请计算item1*item2的最大值 while循环 奇偶数判断 使用input函数接收用户输入的整数，如果是偶数，则使用print函数输出”你输入的是一个偶数”,反之输出”你输入的是一个奇数”，用户可以输入多次，直到输入quit时程序退出
1 2 3 4 5 6 7 8 9 10 while True : input_str = input ("请输入一个正整数，想退出程序请输入 quit:" ) if input_str == "quit" : break number = int (input_str) if number % 2 == 0 : print ("你输入的是一个偶数" ) else : print ("你输入的是一个奇数" )
for循环与while循环嵌套 已知 lst = [2, 3, 4]
1 2 3 4 5 6 7 8 9 10 11 lst = [2 , 3 , 4 ] for item in lst: while True : input_str = input ("请输入{number}的倍数,想停止输入时，输入quit:" .format (number=item)) if input_str == 'quit' : break number = int (input_str) if number % item == 0 : print ("输入正确" ) else : print ("输入错误" )
continue的好处 break是跳出循环体，continue是跳过continue语句后面的代码块，循环并不停止
题目要求：
1 2 3 4 5 6 7 8 9 10 11 12 while True : input_str = input ("请输入一个正整数,如果想停止程序，输入quit:" ) if input_str == 'quit' : break number = int (input_str) if number > 10 : continue if number % 2 == 0 : print ("输入为偶数" ) else : print ("输入为奇数" )
当number大于10 的时候，后面的那4行代码就不会被执行，直接进入到下一次循环。
上面的代码，也可以不使用continue
1 2 3 4 5 6 7 8 9 10 while True : input_str = input ("请输入一个正整数,如果想停止程序，输入quit:" ) if input_str == 'quit' : break number = int (input_str) if number < 10 : if number % 2 == 0 : print ("输入为偶数" ) else : print ("输入为奇数" )
两段代码，实现了一样的功能，但对比一下不难发现，使用了不使用continue，代码的嵌套层次更深，如果嵌套多了，会让代码变得难以阅读，难以管理
但使用continue，就可以减少代码层次，代码的理解和管理都更容易，大于10的时候，continue跳过后面的代码，在逻辑思考时，这种一刀两断的方法让思路更清晰。
内置函数篇 本篇的练习题不是考察你如何使用python的内置函数，而是通过实现与内置函数相同功能的函数来达到锻炼提升编码能力的目的
abs 题目要求 abs函数返回数字的绝对值，请实现下面的函数，模仿abs函数的功能,返回数字的绝对值
1 2 def my_abs (number ): pass
思路分析 处于程序健壮性考虑，要对传入的number参数进行检查，判断其类型是否为数字类型，float和int是比较常用的数据类型，复数类型基本接触不到，因此不考虑。
判断变量类型，可以使用isinstance函数，该函数的第一个参数是需要检查类型的对象，第二个参数可以是数据类型，也可以是一个元组，元组里是多个数据类型，只要满足其中一个就返回True
如果number的数值小于0，乘以-1就得到了绝对值
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def my_abs (number ): if not isinstance (number, (float , int )): return number if number < 0 : number *= -1 return number if __name__ == '__main__' : print (my_abs(-3 )) print (my_abs(-3.9 )) print (my_abs(54.3 ))
sum 题目要求 sum函数可以获取列表所有数据的总和，模仿这个功能实现下面的函数，
1 2 3 4 5 6 7 8 def my_sum (lst ): """ 返回列表里所有数据的总和 如果列表里有非数字类型的数据，忽略不管 :param lst: :return: """ pass
思路分析 对传入的参数lst，要进行类型检查 遍历列表，遇到数字类型的数据就进行加和操作 示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def my_sum (lst ): """ 返回列表里所有数据的总和 :param lst: :return: """ sum_res = 0 if not isinstance (lst, list ): return sum_res for item in lst: if isinstance (item, (float , int )): sum_res += item return sum_res if __name__ == '__main__' : lst = [3 , 4 , '43' , 5.4 ] print (my_sum(lst))
max max函数返回序列中的最大值，传入的参数可以是列表，也可以是元组，实现下面的函数，实现同样的功能，如果序列里有非数字类型的数据，可以忽略,如果序列是空的，可以直接返回None
1 2 3 4 5 6 def my_max (seq ): """ 返回序列里的最大值 :param lst: :return: """
思路分析 对传入的参数seq要进行类型检查，如果既不是列表，也不是元组，那么就返回None
如果序列是空的，也可以直接返回None
遍历序列里的元素，如果数据的类型不属于数字类型，那么就忽略该数据
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 def my_max(seq): """ 返回序列里的最大值 :param lst: :return: """ max_value = None if not isinstance(seq, (list, tuple)): return max_value if len(seq) == 0: return max_value max_value = seq[0] for item in seq: if not isinstance(item, (float, int)): continue if item > max_value: max_value = item return max_value if __name__ == '__main__': lst = [3, 4, '43', 5.4] print(my_max(lst))
min min函数返回序列中的最小值，传入的参数可以是列表，也可以是元组，实现下面的函数，实现同样的功能，如果序列里有非数字类型的数据，可以忽略
1 2 3 4 5 6 7 def my_min (seq ): """ 返回序列里的最小值 :param lst: :return: """ pass
思路分析 整体思路与3.3的my_max函数相同
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 def my_min (seq ): """ 返回序列里的最小值 :param lst: :return: """ min_value = None if not isinstance (seq, (list , tuple )): return min_value if len (seq) == 0 : return min_value min_value = seq[0 ] for item in seq: if not isinstance (item, (float , int )): continue if item < min_value: min_value = item return min_value if __name__ == '__main__' : lst = [3 , 4 , '43' , 5.4 ] print (my_min(lst))
int 内置函数int，可以将float,全是数字的字符串转成int类型的数据，为了降低难度，这个练习题只要求你实现其中一种功能，将全是由数字组成的字符串转成int类型数据，例如将字符串”432” 转成整数432，函数定义如下
1 2 3 4 5 6 7 8 9 def my_int (string ): """ 将字符串string转成int类型数据 不考虑string的类型,默认就是符合要求的字符串 传入字符串"432" 返回整数432 :param string: :return: """ pass
思路分析 题目的要求非常明确，只将”432”这种全是由数字组成的字符串转成int类型数据，这样就没什么难度了
遍历字符串，每个将字符串里的每个字符转成int类型的数值，这个过程可以使用字典来完成，建立一个字典，字符串的数字做key，int类型的数字做value,例如下面的字典
1 2 3 4 5 6 7 8 9 10 11 12 str_int_dic = { '0' : 0 , '1' : 1 , '2' : 2 , '3' : 3 , '4' : 4 , '5' : 5 , '6' : 6 , '7' : 7 , '8' : 8 , '9' : 9 }
得到数字后，还得考虑这个数字是哪一位的，是千位还是百位，这里可以使用一个技巧，遍历的过程是从左向右进行的，设置一个变量保存转换后的int数据，初始值赋为0，每一次循环后，都用这个变量乘10再加上所遍历到数值，这样就巧妙的解决了位数问题。
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 str_int_dic = { '0' : 0 , '1' : 1 , '2' : 2 , '3' : 3 , '4' : 4 , '5' : 5 , '6' : 6 , '7' : 7 , '8' : 8 , '9' : 9 } def my_int (string ): """ 将字符串string转成int类型数据 不考虑string的类型,默认就是符合要求的字符串 传入字符串"432" 返回整数432 :param string: :return: """ res = 0 for item in string: int_value = str_int_dic[item] res = res*10 + int_value return res if __name__ == '__main__' : print (my_int('432' ))
str 题目要求 内置函数str的功能非常强大，想要模仿实现一个相同功能的函数是非常困难的，因此本练习题只要求你将int类型的数据转换成字符串，实现下面的函数
1 2 3 4 5 6 7 def my_str (int_value ): """ 将int_value转换成字符串 :param int_value: :return: """ pass
思路分析 int类型的数据，不能像字符串那样使用for循环进行遍历，但可以结合 / 和 % 操作符从个位向高位进行遍历，获取到某一位的数字之后，将其转换成字符串，append到一个列表中。
遍历结束之后，翻转列表，用空字符串join这个列表，即可得到转换后的字符串。
单个数字，如何转成字符串呢？可以使用3.6中类似的方法，创建一个字典，数字为key，字符串数字为value
1 2 3 4 5 6 7 8 9 10 11 12 int_str_dict = { 0 : '0' , 1 : '1' , 2 : '2' , 3 : '3' , 4 : '4' , 5 : '5' , 6 : '6' , 7 : '7' , 8 : '8' , 9 : '9' , }
获得某一位数字后，通过字典获得对应的字符串，此外，还可以通过ascii码表来获得与之对应的数字字符。以3为例，chr(3+48)即可得到字符串’3’，其原理，字符串3的ascii码表十进制数值为51，恰好比3大48，其他数值，也同样如此。
大致的思路已经清晰了，接下来是一些细节问题
如果传入的参数是0，那么直接返回字符串’0’ 如果传入的参数是负数，需要标识记录，最后在列表里append一个’-‘ 字符串。 lst = [1, 2, 3],想要翻转，lst = lst[::-1] 示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 def my_str (int_value ): """ 将int_value转换成字符串 :param int_value: :return: """ if int_value == 0 : return '0' lst = [] is_positive = True if int_value < 0 : is_positive = False int_value = abs (int_value) while int_value: number = int_value%10 int_value //= 10 str_number = chr (number+48 ) lst.append(str_number) if not is_positive: lst.append('-' ) lst = lst[::-1 ] return '' .join(lst) if __name__ == '__main__' : print (my_str(0 )) print (my_str(123 )) print (my_str(-123 ))
float 题目要求 为了降低难度，本题目只要求你将字符串转换成float类型的数据，且字符串都是符合”xx.xx“格式的字符串，例如”34.22”
1 2 3 4 5 6 7 def my_float (string ): """ 将字符串string转换成float类型数据 :param string: :return: """ pass
题目分析 使用split函数，以”.”做分隔符，可以将字符串分割为两部分，整数部分和小数部分，这两个部分可以分别用3.5 中的my_int 函数进行处理，以”34.22”为例，分别得到整数34 和22，对于22，不停的乘以0.1，知道它的数值小于1，就得到了小数部分
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 str_int_dic = { '0' : 0 , '1' : 1 , '2' : 2 , '3' : 3 , '4' : 4 , '5' : 5 , '6' : 6 , '7' : 7 , '8' : 8 , '9' : 9 } def my_int (string ): """ 将字符串string转成int类型数据 不考虑string的类型,默认就是符合要求的字符串 传入字符串"432" 返回整数432 :param string: :return: """ res = 0 for item in string: int_value = str_int_dic[item] res = res*10 + int_value return res def my_float (string ): """ 将字符串string转换成float类型数据 :param string: :return: """ arrs = string.split('.' ) int_value = my_int(arrs[0 ]) float_value = my_int(arrs[1 ]) while float_value > 1 : float_value *= 0.1 return int_value + float_value if __name__ == '__main__' : print (my_float("34.22" ))
len 题目要求 内置函数可以获得可迭代对象的长度，例如字符串，列表，元组，字典，集合。实现一个类似功能的函数，获得数据的长度。
1 2 3 4 5 6 7 def my_len (obj ): """ 获得obj对象的长度 :param obj: :return: """ pass
思路分析 使用for循环遍历对象，循环的次数就是这个对象的长度，只需要一个变量来保存循环的次数就可以了。
对obj参数的检查，可以使用isinstance判断是否为列表，元组，字典，集合，字符串中的某一个，更为简便的做法，这些对象都是可迭代对象，isinstance(obj, Iterable) 可以判断obj是否为可迭代对象
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 from collections import Iterabledef my_len (obj ): """ 获得obj对象的长度 :param obj: :return: """ if not isinstance (obj, Iterable): return None length = 0 for item in obj: length += 1 return length if __name__ == '__main__' : print (my_len('232' )) print (my_len([3 , 4 , 2 , 1 ])) print (my_len({'a' : 4 , 'b' : 4 })) print (my_len((3 , 5 , 6 , 6 , 3 ))) print (my_len(set ([3 , 5 , 6 , 6 , 3 ])))
enumerate 题目要求 enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中，下面是使用示例
1 2 3 lst = ['a' , 'b' , 'c' ] for index, item in enumerate (lst): print (index, item)
程序输出
请仿造该功能实现下面的函数
1 2 3 4 5 6 7 def my_enumerate (lst ): """ 实现和enumerate 类似的功能 :param lst: :return: """ pass
思路分析 想要实现这个函数，只需两行代码就可以了,不过，这需要你对生成器有一定的理解和认识。
yield有着和return相似的功能，都会将数据返回给调用者，不同之处在于，return执行后，函数结束了，而yield执行后，会保留当前的状态，等到下一次执行时，恢复之前的状态，继续执行。
在函数内部，使用for循环通过索引
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 def my_enumerate (lst ): """ 实现和enumerate 类似的功能 :param lst: :return: """ for i in range (len (lst)): yield i, lst[i] lst = ['a' , 'b' , 'c' ] for index, item in my_enumerate(lst): print (index, item)
all 题目要求 all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 True，示例代码如下
1 2 lst = [True , False , True ] print (all (lst))
最终输出结果是False,实现下面的函数，完成类似的功能
1 2 3 4 5 6 7 def my_all (seq ): """ 如果列表里所有的元素都是True,则函数返回True,反之,返回False :param seq: 列表 :return: """ pass
为了简化难度，参数seq默认只传列表
思路分析 老规矩，使用for循环遍历列表，当前遍历到的元素如果是False，直接返回False
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def my_all (seq ): """ 如果列表里所有的元素都是True,则函数返回True,反之,返回False :param seq: 列表 :return: """ for item in seq: if not item: return False return True if __name__ == '__main__' : print (my_all([True , False , True ]))
any 题目要求 any函数用于判断给定的可迭代参数 iterable 中的所有元素是否至少有一个为True
1 2 lst = [True , False , False ] print (any (lst))
输出结果为True
1 2 3 4 5 6 7 def my_any (lst ): """ 列表lst中有一个True,则函数返回True :param lst: :return: """ pass
思路分析 老规矩，遍历列表，当前遍历到的元素如果为True，则函数返回True
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def my_any (lst ): """ 列表lst中有一个True,则函数返回True :param lst: :return: """ for item in lst: if item: return True return False if __name__ == '__main__' : print (my_any([True , False , False ]))
bin 函数bin可以获得整数的二进制形式，示例代码如下
程序输出结果为0b1010。
实现下面的函数，完成相同的功能，为了降低难度，你的算法只需要考虑正整数，而且二进制前面不需要加0b
1 2 3 4 5 6 def my_bin (value ): """ 返回正整数value的二进制形式 :param value: :return: """
思路分析 在算法面试中，有一道题目经常被使用，它要求应聘者计算一个整数的二进制中1的个数。解决的思路是判断二进制最后一位是否为1，如果为1，则计数器加1，判断完成后，整数向右位移一位（使用位运算符 >>） ，继续判断二进制的最后一位是否为1.
本练习题可以采用相同的思路
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def my_bin (value ): """ 返回正整数value的二进制形式 :param value: :return: """ lst = [] while value: if value % 2 == 1 : lst.append('1' ) else : lst.append('0' ) value = value >>1 lst = lst[::-1 ] return '' .join(lst) print (bin (10 ))if __name__ == '__main__' : print (my_bin(3 )) print (my_bin(8 )) print (my_bin(10 ))
字符串方法 find 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 def my_find (source, target, start=0 ): """ 返回字符串source中 子串target开始的位置， 从start索引开始搜索 如果可以找到多个，返回第一个 :param source: :param target: :param start: :return: """ if not source or not target: return -1 if start < 0 or start >= len (source): return -1 if len (target) > len (source): return -1 for index in range (start, len (source) - len (target)+1 ): t_index = 0 while t_index < len (target): if target[t_index] == source[t_index+index]: t_index += 1 else : break if t_index == len (target): return index return -1 if __name__ == '__main__' : print (my_find('this is a book' , 'this' )) print (my_find('this is a book' , 'this' , start=1 )) print (my_find('this is a book' , 'book' )) print (my_find('this is a book' , 'k' , start=10 )) print (my_find('this is a book' , 'book' , start=10 )) print (my_find('this is a book' , 'a' , start=3 ))
replace 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 def my_replace (source, oldsub, newsub ): """ 将字符串里所有的oldsub子串替换成newsub :param source: :param old: :param new: :return: """ if not source or not oldsub: return source new_string = "" start_index = 0 index = my_find(source, oldsub, start=start_index) while index != -1 : new_string += source[start_index:index] + newsub start_index = index+len (oldsub) index = my_find(source, oldsub, start=start_index) new_string += source[start_index:] return new_string def my_find (source, target, start=0 ): """ 返回字符串source中 子串target开始的位置， 从start索引开始搜索 如果可以找到多个，返回第一个 :param source: :param target: :param start: :return: """ if not source or not target: return -1 if start < 0 or start >= len (source): return -1 if len (target) > len (source): return -1 for index in range (start, len (source) - len (target)+1 ): t_index = 0 while t_index < len (target): if target[t_index] == source[t_index+index]: t_index += 1 else : break if t_index == len (target): return index return -1 if __name__ == '__main__' : print (my_replace('this is a book' , 'this' , 'it' )) print (my_replace('this is a this book' , 'this' , 'it' )) print (my_replace('this is a this bookthis' , 't2his' , 'it' ))
split 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 def my_find (source, target, start=0 ): """ 返回字符串source中 子串target开始的位置， 从start索引开始搜索 如果可以找到多个，返回第一个 :param source: :param target: :param start: :return: """ if not source or not target: return -1 if start < 0 or start >= len (source): return -1 if len (target) > len (source): return -1 for index in range (start, len (source) - len (target)+1 ): t_index = 0 while t_index < len (target): if target[t_index] == source[t_index+index]: t_index += 1 else : break if t_index == len (target): return index return -1 def my_split (source, sep, maxsplit=-1 ): """ 以sep分割字符串source :param source: :param sep: :param maxsplit: :return: """ if not source or not sep: return [] lst = [] max_split_count = maxsplit if maxsplit >0 else len (source) split_count = 0 start_index = 0 index = my_find(source, sep, start=start_index) while split_count < max_split_count and index != -1 : sep_str = source[start_index:index] lst.append(sep_str) split_count += 1 start_index = index + len (sep) index = my_find(source, sep, start=start_index) sep_str = source[start_index:] lst.append(sep_str) return lst if __name__ == '__main__' : print (my_split("1,3,4" , ',' )) print (my_split("1,,3,,4" , ',,' )) print (my_split("abcadae" , 'a' )) print (my_split("abcadae" , 'a' , maxsplit=2 )) print (my_split("aaaa" , 'a' ))
字符串大写转小写 题目要求 实现函数
1 2 3 4 5 6 def lower (string ): """ 将字符串string里所有的大写字母改成小写字母，并返回一个新的字符串 :param string: :return: """
思路分析 实现大小写转换，首先要能识别出一个字符是否为大写字母，你可以在得到这个字符后，判断其是否在A和Z之间，更专业的办法是通过ord 函数获得这个字符的ASCII码表的十进制数值，判断其是否在65和90之间。
获得字符的ASCII码表的十进制数值，其目的不仅仅是判断它是否为大写字母，第二个目的是通过这个十进制数值与32相加，来获得大写字母所对应的小写字母的十进制数值，这样，才能准确的转换成小写字母。
我在程序里使用list函数将字符串转成列表，之所以这样做，是因为字符串是不可变类型的数据，无法直接修改，只好先将其转成列表，将列表里的大写字母转成小写字母，再将列表转成字符串。
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def lower (string ): """ 将字符串string里所有的大写字母改成小写字母，并返回一个新的字符串 :param string: :return: """ if not string: return None lst = list (string) for index, item in enumerate (lst): ascii_index = ord (item) if 65 <= ascii_index <= 90 : s = chr (ascii_index+32 ) lst[index] = s return '' .join(lst) if __name__ == '__main__' : print (lower('232rSFD' ))
判断字符串是否全部为小写字母 题目要求 实现函数
1 2 3 4 5 6 7 def islower (string ): """ 如果字符串string 里所有区分大小写的字符都是小写，则返回True :param string: :return: """ pass
比如传入字符串 “iwj32as”，函数应该返回True
思路分析 字符串里，常见的只有26个英文字母是区分大小写的，因为，咱们只关心英文字母即可。
遍历字符串，逐个字符进行检查，获得其ASCII码表里的十进制数值，如果该数值在65到90之间，一定是大写字母，此时返回False，如果for循环结束后，仍然没有返回False，那么就说明，字符串里没有大写字母，可以返回True
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def islower (string ): """ 如果字符串string 里所有区分大小写的字符都是小写，则返回True :param string: :return: """ if not string: return False for item in string: if 65 <= ord (item) <= 90 : return False return True if __name__ == '__main__' : print (islower('232r' ))
实现isdigit 题目要求 实现函数isdigit， 判断字符串里是否只包含数字0~9
1 2 3 4 5 6 7 def isdigit (string ): """ 判断字符串只包含数字 :param string: :return: """ pass
思路分析 遍历字符串，对每个字符做检查，如果都是0到9的某个数值，那么函数返回True，只要有一个不是0到9，就返回False。
如何确定一个字符是不是0到9中的某一个呢，方法很多，你可以用if条件判断语句判断字符是否在列表[‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’]中，也可以像我下面示例代码一样，使用ord函数获得字符的ASCII编码对应的10进制数值，接着判断是否在48到57之间。
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def isdigit (string ): """ 判断字符串只包含数字 :param string: :return: """ if not string: return False for item in string: if not (48 <= ord (item) <= 57 ): return False return True if __name__ == '__main__' : print (isdigit('232' )) print (isdigit('232r' )) print (isdigit('' ))
startswith 题目要求 实现函数is_startswith，如果字符串source是以substr开头的，则函数返回True,反之返回False
1 2 3 4 5 6 7 8 def is_startswith (source, substr ): """ 判断字符串source是否以substr开头 :param source: :param substr: :return: """ pass
思路分析 函数首先要判断传入的参数是否合法，这里默认传入的都是字符串，那么我们要需要判断字符串是否有空串的情况
如果substr的长度大于source的长度，直接返回False
从索引0开始，遍历substr,从source上获得相同索引的字符，两者进行比较，只要有一个字符不相同，则可以立即返回False
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def is_startswith (source, substr ): """ 判断字符串source是否以substr开头 :param source: :param substr: :return: """ if not source or not substr: return False if len (substr) > len (source): return False for index, item in enumerate (substr): if item != source[index]: break else : return True return False if __name__ == '__main__' : print (is_startswith("python" , 'py' ))
endswith 题目要求 实现函数is_endswith，判断字符串source是否以substr结尾
1 2 3 4 5 6 7 8 def is_endswith (source, substr ): """ 判断字符串source 是否以substr结尾 :param source: :param substr: :return: """ pass
思路分析 这个练习题的解法其实和is_startswith函数相差无几，所不同的是，在is_startswith函数中，要从索引0开始进行相同位置字符的比较，而现在，是要判断是否以substr结尾，所以我们从索引len(source) - len(substr)开始逐一进行比较
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def is_endswith (source, substr ): """ 判断字符串source 是否以substr结尾 :param source: :param substr: :return: """ if not source or not substr: return False if len (substr) > len (source): return False start_index = len (source) - len (substr) for index in range (start_index, len (source)): if source[index] != substr[index-start_index]: break else : return True return False if __name__ == '__main__' : print (is_endswith("python" , 'thon' ))
实现字符串capitalize方法 题目要求 capitalize方法将字符串的第一个字母转成大写，其他字母转成小写，请实现函数my_capitalize，完成同样的功能
1 2 def my_capitalize (string ): pass
思路分析 遍历字符串，如果首字母是小写，则转成大写，其余索引上的字母如果是大写，则转成小写
大小写转换的方法，可以参考lower函数的实现
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def my_capitalize (string ): if not string: return string lst = [] for index, item in enumerate (string): ascii_index = ord (item) if index == 0 : if 97 <= ascii_index <= 122 : item = chr (ascii_index-32 ) else : if 65 <= ascii_index <= 90 : item = chr (ascii_index+32 ) lst.append(item) return "" .join(lst) print (my_capitalize('this is A book' ))
实现字符串count方法 题目要求 字符串count方法，可以返回指定范围内的子串的数量，下面是用法示例
1 2 3 4 source = "this is a book" target = 'is' print (source.count(target))
程序输出2
请仿照字符串的count方法，实现下面的函数
1 2 3 4 5 6 7 8 9 10 def my_count (source, target, start, end ): """ 函数返回字符串source在start 和 end之前，子串target 的数量， 索引范围左闭右开 :param source: :param target: :param start: :param end: :return: """ pass
思路分析 对于传入的参数进行合法性判断，是编写函数时必须要考虑的事情
字符串source，target为空判断 start >= end判断 start范围判断，不能小于0，也不能大于等于len(source) 如果end大于len(source)，则重新对end赋值，让其等于len(source)，算是一种合理的补救 经过前面的4个判断后，基本上可以保证传入的参数是合法的，不至于因为参数不合法导致程序出错
具体实现思路，将字符串target索引0与字符串source索引start进行对齐，然后逐个字符比较，只要有一个不相同，就说明，source[start: len(target)] != target，那么就需要向右移动一位，比较source[start+1: len(target)]是否与target相等。
代码里最精髓的是if t_index == len(target)这行，如果对比过程中，触发了break，那么t_index一定不会与len(target)相等，就依靠这个条件判断，就可以知道是不是找到了子串。
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 def my_count (source, target, start, end ): """ 函数返回字符串source在start 和 end之前，子串target 的数量， 索引范围左闭右开 :param source: :param target: :param start: :param end: :return: """ if not source or not target: return 0 if start >= end: return 0 if start >= len (source) or start < 0 : return 0 count = 0 if end > len (source): end = len (source) index = start while index < end: t_index = 0 while t_index < len (target) and index+len (target) <= end: if target[t_index] != source[index+t_index]: break t_index += 1 if t_index == len (target): index += len (target) count += 1 else : index += 1 return count source = "this is a book" target = 'is' print (my_count(source, target, 0 , len (source)))
排序算法篇 排序算法最能体现一个程序员的算法功底，也是面试时经常被拿来考察候选者的题目，本篇章一共讲解8种排序算法。
冒泡排序 冒泡排序的核心思想是相邻的两个数据进行比较，假设数列A有n个数据，先比较第1个和第2个数据，如果A1 > A2,则交换他们的位置，确保较大的那个数在右侧。
接下来比较A2和A3，采用相同的规则，较大的数向右移动，最后会比较An-1 和An的大小，如果An-1 > An，那么交换他们的位置，这时，An是数列中的最大值。
你肯定已经发现，经过这一轮比较后，数列仍然是无序的，但是没有关系，我们已经找到了最大值An，而且它在队列的末尾。
接下来要做的事情，就是简单的重复之前的过程，整个数列，先暂时把An排除在外，这n-1个无序的数，仍然可以采用之前的方法，找出n-1个数当中的最大值，这样An-1就是第2大的数，继续对n-2个数做相同的事情
为了让你更容易理解冒泡排序，我们先实现一个简单的函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def move_max (lst, max_index ): """ 将索引0到max_index这个范围内的最大值移动到max_index位置上 :param lst: :param max_index: :return: """ for i in range (max_index): if lst[i] > lst[i+1 ]: lst[i], lst[i+1 ] = lst[i+1 ], lst[i] if __name__ == '__main__' : lst = [7 , 1 , 4 , 2 , 3 , 6 ] move_max(lst, len (lst)-1 ) print (lst)
这个函数只完成一个简单的功能，它将列表从索引0到max_index之间的最大值移动max_index索引上，这正是冒泡排序的核心思想。
当我们完成这一步，剩下的事情，就是不断的重复这个过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def pop_sort (lst ): for i in range (len (lst)-1 , 1 , -1 ): move_max(lst, i) def move_max (lst, max_index ): """ 将索引0到max_index这个范围内的最大值移动到max_index位置上 :param lst: :param max_index: :return: """ for i in range (max_index): if lst[i] > lst[i+1 ]: lst[i], lst[i+1 ] = lst[i+1 ], lst[i] if __name__ == '__main__' : lst = [7 , 1 , 4 , 2 , 3 , 6 ] pop_sort(lst) print (lst)
快速排序 快速排序的思路可以归结为3个步骤
从待排序数组中随意选中一个数值，作为基准值 移动待排序数组中的元素，是的基准值左侧的数值都小于等于它，右侧的数值大于等于它 基准值将原来的数组分为两部分，针对这两部分，重复步骤1，2， 3 通过分析，可以确定，必然要使用递归算法，遇到递归不要害怕，先把1，2两步分区实现，最后实现第3步的递归
先实现分区
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def partition (lst,start,end ): """ 用lst[start] 做基准值，在start到end这个范围进行分区 """ pivot = lst[start] while start < end : while start < end and lst[end] >= pivot: end -= 1 lst[start] = lst[end] while start < end and lst[start] <= pivot: start += 1 lst[end] = lst[start] lst[start] = pivot return start
partition函数返回基准值最后的索引，知道这个索引，才能将之前的待排序数组分为两部分，下面是递归部分的实现
1 2 3 4 5 6 7 def my_quick_sort (lst,start,end ): if start>= end: return index = partition(lst,start,end) my_quick_sort(lst,start,index-1 ) my_quick_sort(lst,index+1 ,end)
虽然这两段代码里的逻辑，你还有些不清楚，但整个的分析过程应该说是比较清晰的，先实现分区，然后实现递归，在编写算法时，很忌讳大包大揽的考虑问题，不分层次，不分先后，不分轻重。
分区虽然没有让整个数组变得有序，但是让基准值找到了自己应该在的位置，对左右两侧重复分区动作，每一次分区动作都至少让一个元素找到自己应该在的位置。
验证代码
1 2 3 4 if __name__ == '__main__' : lst = [4 ,3 ,2 ,4 ,1 ,5 ,7 ,2 ] my_quick_sort(lst,0 ,len (lst)-1 ) print lst
希尔排序 算法定义 希尔排序，又称缩小增量排序，不要被这个名字吓到，其实，它只是对插入算法的改进而已。
当待排序列基本有序的情况下，插入算法的效率非常高，那么希尔排序就是利用这个特点对插入算法进行了改造升级
分组 待排序数组为
1 4 ,1 ,67 ,34 ,12 ,35 ,14 ,8 ,6 ,19
第一轮希尔排序 希尔排序的关键在于对待排序列进行分组，这个分组并不是真的对序列进行了拆分，而仅仅是虚拟的分组
首先，用10/2 = 5, 这里的5就是缩小增量排序中的那个“增量”。从第0个元素开始，每个元素都与自己距离为5的元素分为一组，那么这样一来分组情况就是
1 2 3 4 5 4 35 1 14 67 8 34 6 12 19
需要注意的是，所谓的分组，仅仅是逻辑上的分组，这10个元素仍然在原来的序列中。上面一共分了5组，每一组都进行插入排序，67 和 8 交换位置，34 和6 交换位置，这样第一次分组后并对各组进行插入排序后，序列变成了
1 4, 1, 8, 6, 12, 35, 14, 67, 34, 19
第二轮希尔排序 上一轮排序时，增量为5，那么这一轮增量为5/2 = 2，这就意味着，从第0个元素开始，每个元素都与自己距离为2的元素分为一组，分组情况如下
1 2 4 8 12 14 34 1 6 35 67 19
整个序列被分成了两组，分别对他们进行插入排序，排序后的结果为
1 4, 1, 8, 6, 12, 19, 14, 35, 34, 67
第三轮希尔排序 上一轮排序时，增量为2，这一轮增量为2 /2 = 1，当增量为1的时候，其实就只能分出一个组了，这样，就完全的退化成插入排序了，但是，由于已经进行了两轮希尔排序，使得序列已经基本有序了，那么此时进行插入排序，效果就会非常好
增量从5变为2，从2变为1，是逐渐减小的过程，增量是分组时所使用的步长。
示例代码 有了前面的概念以及算法的理解，写出代码就变得容易了，先分组，然后进行插入排序，你唯一要注意的地方是进行插入排序时，要弄清楚，哪些元素是一组的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 lst = [4 ,1 ,67 ,34 ,12 ,35 ,14 ,8 ,6 ,19 ] length = len (lst) step = length//2 while step > 0 : for i in range (step): for j in range (i+step, length, step): if lst[j] < lst[j-step]: tmp = lst[j] k = j-step while k >= 0 and lst[k] > tmp: lst[k+step] = lst[k] k -= step lst[k+step] = tmp step //= 2 print lst
归并排序 合并两个有序集合 有两个有序的序列，分别为 [1,4,7] ,[2,3,5],现在请考虑将这两个序列合并成一个有序的序列。
其实方法真的非常简单
首先创建一个新的序列，分别从两个序列中取出第一个数，1和2，1比2小，把1放到新的序列中 第一个序列中的1已经放到新序列中，那么拿出4来进行比较，2比4小，把2放到新的序列中 第二个序列中的2已经放到新序列中，那么拿出3来进行比较，3比4小，把3放到新的序列中 第二个序列中的3已经放到新序列中，那么拿出5来进行比较，4比5小，把4放到新的序列中 第一个序列中的4已经放到新序列中，那么拿出7来进行比较，5比7小，把5放到新的序列中 最后把7放入到新的序列中 合并的方法就是分别从两个序列中拿出一个数来进行比较，小的那一个放到新序列中，然后，从这个小的数所属的序列中拿出一个数来继续比较
示例代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def merge_lst (left_lst,right_lst ): left_index, right_index = 0 , 0 res_lst = [] while left_index < len (left_lst) and right_index < len (right_lst): if left_lst[left_index] < right_lst[right_index]: res_lst.append(left_lst[left_index]) left_index += 1 else : res_lst.append(right_lst[right_index]) right_index += 1 if left_index == len (left_lst): res_lst.extend(right_lst[right_index:]) else : res_lst.extend(left_lst[left_index:]) return res_lst
归并排序 归并排序，利用了合并有序序列的思想，把一个序列分成A,B两个序列，如果这两个序列是有序的，那么直接合并他们不就可以了么，但是A，B两个序列未必是有序的，没关系，就拿A序列来说，我把A序列再分一次，分成A1,A2，如果A1，A2有序我直接对他们进行合并，A不就变得有序了么，但是A1，A2未必有序啊，没关系，我继续分，直到分出来的序列里只有一个元素的时候，一个元素，就是一个有序的序列啊，这个时候不就可以合并了
这样一层一层的分组，分到最后，一个组里只有一个元素，终于符合合并的条件了，再一层一层的向上合并
完成示例代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 def merge_lst (left_lst,right_lst ): left_index, right_index = 0 , 0 res_lst = [] while left_index < len (left_lst) and right_index < len (right_lst): if left_lst[left_index] < right_lst[right_index]: res_lst.append(left_lst[left_index]) left_index += 1 else : res_lst.append(right_lst[right_index]) right_index += 1 if left_index == len (left_lst): res_lst.extend(right_lst[right_index:]) else : res_lst.extend(left_lst[left_index:]) return res_lst def merge_sort (lst ): if len (lst) <= 1 : return lst middle = len (lst)//2 left_lst = merge_sort(lst[:middle]) right_lst = merge_sort(lst[middle:]) return merge_lst(left_lst, right_lst) if __name__ == '__main__' : lst = [19 ,4 ,2 ,8 ,3 ,167 ,174 ,34 ] print merge_sort(lst)
选择排序 假设有一个序列，a[0],a[1],a[2]…a[n]现在，对它进行排序。我们先从0这个位置到n这个位置找出最小值，然后将这个最小值与a[0]交换，然后呢，a[1]到a[n]就是我们接下来要排序的序列
我们可以从1这个位置到n这个位置找出最小值，然后将这个最小值与a[1]交换，之后，a[2]到a[n]就是我们接下来要排序的序列
每一次，我们都从序列中找出一个最小值，然后把它与序列的第一个元素交换位置，这样下去，待排序的元素就会越来越少，直到最后一个
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 def select_sort (lst ): for i in range (len (lst)): min = i for j in range (min ,len (lst)): if lst[min ] > lst[j]: min = j lst[i], lst[min ] = lst[min ], lst[i] lst = [2 ,6 ,1 ,8 ,2 ,4 ,9 ] select_sort(lst) print lst
堆排序 堆的概念 堆是一种数据结构，分最大堆和最小堆，最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。
我们用list来描述它
1 lst = [9 , 6 , 8 , 3 , 1 , 4 , 2 ]
你看不出这个lst有什么特别，别着急，再介绍两个概念给你
父节点，子节点 列表中的每一个元素都是一个节点，以lst[0] 为例，他的子节点分别是lst[1],lst[2]，同时我们也说lst[1]的父节点是lst[0]
我们可以计算每一个节点的子节点，假设当前节点的序号是i，那么它的左子节点则是 i2 +1,右子节点则是i 2 + 2
最大堆，最小堆 所谓最大堆就是指每一个节点的值都比它的子节点的值大，最小堆就是指每一个节点的值都比它的子节点的值小
现在，我们再来看上面给出的列表
lst[0] = 9,它的子节点分别是lst[1]=6,lst[2]=8
lst[1] = 6,它的子节点分别是lst[3]=3,lst[4]=1
lst[2] = 8,它的子节点分别是lst[5]=4,lst[6]=2
lst[3] = 3,它的子节点分贝是lst[7]和lst[8]，但这两个节点是不存在的
后面的也就不用再看了，这个列表符合最大堆的要求，父节点的值大于两个子节点的值，而且最重要的一点，堆中任意一颗子树仍然是堆
如何建立一个堆 关于堆的应用，非常多，比如堆排序，在应用之前，我们必须先建立一个堆，刚才给出的列表，恰好是一个堆，如果不是堆呢，我们需要将其变成堆，例如下面这个列表
1 lst = [3 , 9 , 2 , 6 , 1 , 4 , 8 ]
这个列表里的元素和上一个列表里的元素是一样的，只是顺序不同，建立堆的过程，就是调整顺序的过程，使其满足堆的定义
不是所有节点都有子节点 如果当前节点的位置是i,那么子节点的位置是i2 + 1 和 i 2 +2 ，因此，不是所有节点都有子节点，假设一个堆的长度为n，那么n/2 - 1 及以前的节点都是有子节点的，这是一个非常简单的算数题，你稍微用脑就能理解。
那么建立堆的过程，就是从n/2 - 1 到0 逐渐调整的过程，如何调整呢？
每个节点都和自己的两个子节点中最大的那个节点交换位置就可以了，这样，节点值较大的那个就会不停的向上调整
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def adjust_heap (lst, i, size ): lchild = 2 * i + 1 rchild = 2 * i + 2 max = i if i < size // 2 : if lchild < size and lst[lchild] > lst[max ]: max = lchild if rchild < size and lst[rchild] > lst[max ]: max = rchild if max != i: lst[max ], lst[i] = lst[i], lst[max ] adjust_heap(lst, max , size) def build_heap (lst ): for i in range ((len (lst)//2 )-1 , -1 , -1 ): adjust_heap(lst, i, len (lst)) print lst lst = [3 ,9 ,2 ,6 ,1 ,4 ,8 ] build_heap(lst) print lst
最大堆，最小堆 关于最大堆，最小堆，我们只要掌握一点就好了，对于最大堆，堆定的元素一定是整个堆里最大的，但是，如果我们去观察，整个堆并不呈现有序的特性，比如前面建立的堆
堆顶元素为9，是最大值，但是从0到最后一个元素，并不是有序的
堆排序的思路 lst = [9, 6, 8, 3, 1, 4, 2]
（1）将lst[0] 与 lst[6]交换，交换后为[2, 8, 6, 4, 3, 1, 9],现在，这个堆已经被破坏掉了
（2）那么我们可以利用adjust_heap函数重新把它调整成一个堆，adjust_heap(lst,0,6)，这样调整后，lst=[8, 6, 4, 3, 1, 2, 9]
注意看lst[0]到lst[5],这个范围内的数据被调整成了一个堆，使得lst[0]也就是8是这个范围内的最大值
我们只需要重复刚才的两个步骤，就可以将堆的大小逐步缩小，同时，从后向前让整个lst变得有序
示例代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 def adjust_heap (lst, i, size ): lchild = 2 * i + 1 rchild = 2 * i + 2 max = i if i < size // 2 : if lchild < size and lst[lchild] > lst[max ]: max = lchild if rchild < size and lst[rchild] > lst[max ]: max = rchild if max != i: lst[max ], lst[i] = lst[i], lst[max ] adjust_heap(lst, max , size) def build_heap (lst ): for i in range ((len (lst)//2 )-1 , -1 , -1 ): adjust_heap(lst, i, len (lst)) print lst lst = [3 ,9 ,2 ,6 ,1 ,4 ,8 ] def heap_sort (lst ): size = len (lst) build_heap(lst) print '*' *20 for i in range (size-1 , -1 , -1 ): lst[0 ], lst[i] = lst[i], lst[0 ] adjust_heap(lst, 0 , i) print lst,i heap_sort(lst) print '*' *20 print lst
插入排序 插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
咱们举一个例子，你就能明白插入排序的精髓所在
lst是一个待排序的列表，你仔细观察不难发现，这个列表里的前4个数据已经是有序的了，现在，只需要把最后一个元素5插入到一个合适的位置就可以了。
从7开始向左遍历，比5大的数向右移动，当遇到一个小于等于5的数就停下来，这个位置就是5应该在的位置。当7向右移动时，占据了5的位置，因此，程序里需要一个变量把5保存下来，还需要一个变量把向左遍历时的索引记录下来，最后这个索引就是5应该在的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def insert (lst, index ): """ 列表lst从索引0到索引index-1 都是有序的 函数将索引index位置上的元素插入到前面的一个合适的位置 :param lst: :param index: :return: """ if lst[index-1 ] < lst[index]: return tmp = lst[index] tmp_index = index while tmp_index > 0 and lst[tmp_index-1 ] > tmp: lst[tmp_index] = lst[tmp_index-1 ] tmp_index -= 1 lst[tmp_index] = tmp if __name__ == '__main__' : lst = [1 , 2 , 6 , 7 , 5 ] insert(lst, 4 ) print (lst)
函数默认列表lst从0到index-1都是有序的，现在只需要将索引index位置上的数据插入到合适的位置就可以了。
你可能已经产生了疑惑，咱们是要排序啊，你这函数默认前面index-1个数据都是有序的，这不合理啊，前面index-1个数据如果是无序的，你怎么办呢？
看下面的代码，你就全明白了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 def insert (lst, index ): """ 列表lst从索引0到索引index-1 都是有序的 函数将索引index位置上的元素插入到前面的一个合适的位置 :param lst: :param index: :return: """ if lst[index-1 ] < lst[index]: return tmp = lst[index] tmp_index = index while tmp_index > 0 and lst[tmp_index-1 ] > tmp: lst[tmp_index] = lst[tmp_index-1 ] tmp_index -= 1 lst[tmp_index] = tmp def insert_sort (lst ): for i in range (1 , len (lst)): insert(lst, i) if __name__ == '__main__' : lst = [1 , 6 , 2 , 7 , 5 ] insert_sort(lst) print (lst)
第1个元素单独看做一个数列，它本身就是有序的，那么只需要执行insert(lst, 1)，就可以保证前两个数据变成有序的，然后执行insert(lst, 2)，此时，从索引0到索引1是有需的，只需要将索引为2的数据插入到合适的位置就可以了。
本网站只是搬运工，资源均来自互联网，如有侵权请联系删除，站长不会以此获取任何利益!
