day10 算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了day10 算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3475字,纯文字阅读大概需要5分钟。
内容图文
![day10 算法](/upload/InfoBanner/zyjiaocheng/666/c67e792f393a4230a15cafa81b3c2f5d.jpg)
?? ?冒泡算法 ? ? ?? ?冒泡排序,把列表竖起来看,就像一个个气泡往上去(时间复杂度大) 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 ?
? ?
内容总结
以上是互联网集市为您收集整理的day10 算法全部内容,希望文章能够帮你解决day10 算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。