冒泡算法 冒泡排序,把列表竖起来看,就像一个个气泡往上去(时间复杂度大) lst = [12,3,3,2424,14,3567,534,324,324,23,4,23,42,4324] for num in range(len(lst)): for i in range(len(lst)-1): if lst[i] > lst[i+1]: lst[i], lst[i+1] = lst[i+1], lst[i] print(lst) 冒泡排序,优化后代码 lst = [12,3,3,2424,14,3567,534,324,324,23,4,23,42,4324] for num in range(len(lst)): for i in range(len(lst)-1-num): #冒完一次泡后, 以后冒泡的时候就可以少冒一个, 依次递减 if lst[i] > lst[i+1]: lst[i], lst[i+1] = lst[i+1], lst[i] print(lst) 二分法: 二分法进行查找,每次能够排除掉一半的数据. 查找效率非常高 要求: 查找的序列必须是有序序列 原生二分法: lst = [1,2,4,5,9,21,23,34,35,56,87,123,231,345,678,999] n = 35 for i in lst: #遍历查找 #最大时间复杂度o(n) if i == n: print('found') break else: print('not found') left = 0 right = len(lst)-1 while left <= right: #使用二分法可以提高效率(有序的才能用这种方法)(一次砍一半) middle = (left + right)//2 #这里必须是整除 if lst[middle] > n: #2**n < 数据量; 比如1亿个数, 27次就可以找到 right = middle - 1 if lst[middle] < n: left = middle + 1 if lst[middle] == n: print('found') break else: print('not found') 递归可以完成二分法 lst = [1,2,4,5,9,21,23,34,35,56,87,123,231,345,678,999] def func(n,left,right): if left <= right: #为啥不用while, 因为用了递归 middle = (left + right)//2 if n > lst[middle]: left = middle + 1 return func(n, left, right) #递归 if n < lst[middle]: right = middle - 1 return func(n, left, right) #递归 #返回值的问题: 如果递归了很多层, 最后一层得到结果,返回给倒数第二层, 就完事了. 如何一层层返回: return 倒数第二层给倒数第三次, 依次类推直到返回给第一层. if n == lst[middle]: print('found') return middle #通过return返回, 不能用break else: print('not found') return -1 #1.模仿find找不到返回 -1(一般index是整数); 2. -1 比 None好运算,可能会用到 rst = func(87, 0, len(lst)-1) print(rst) 查找最快的方案 lst1 = [2,3,5,6,8] lst2 = [0 for i in range(max(lst1)+1)] #找到列表中最大的数, 作为都是 0 的新列表的长度 for el in lst1: #把数字变成index lst2[el] = 1 n = 1 if lst2[n] == 1: #优点o(1) 时间复杂度, 空间复杂度最低 print('it is in') else: print('it not in') 3.c3算法 class A: pass class B(A): pass class C(B): pass class D: pass class E(D,C): pass class F: pass class G(F): pass class H(C,G): pass class Foo(E,H): pass #c3算法: #自己先拿出来, 最优先,先安放好 L(E) = D,object + C,B,A,object #拿出第一个的表头,和第二个(除表头)比, 如果没有相等的, 把第一个表头去掉安放好 >>>E,D,C,B,A,object #如果有相等的, 第一个表头就不动, 然后从第二个拿出表头, 和第一个(除表头比) #依次类推, c3 算法可以得到继承顺序 L(H) = C,B,A,object + G,F,object >>>H,C,B,A,G,F,object L(Foo) = E + H L(Foo) = E,D,C,B,A,object + H,C,B,A,G,F,object >>>Foo,E,D,H,C,B,A,G,F,object