2023年6月29日发(作者：)

python的四⼤算法及实例1、什么是算法算法(algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。mark：我们可以把所有的算法想象为⼀本“菜谱”，特定的算法⽐如菜谱中的的⼀道“⽼醋花⽣⽶”的制作流程，只要按照菜谱的要求制作⽼醋花⽣⽶，那么谁都可以做出⼀道好吃的⽼醋花⽣⽶。so，这个做菜的步骤就可以理解为：“解决问题的步骤”2、算法的意义假设计算机⽆限快，并且计算机存储容器是免费的，我们还需要各种乱七⼋糟的算法吗？如果计算机⽆限快，那么对于某⼀个问题来说，任何⼀个都可以解决他的正确⽅法都可以的！当然，计算机可以做到很快，但是不能做到⽆限快，存储也可以很便宜但是不能做到免费。那么问题就来了效率：解决同⼀个问题的各种不同算法的效率常常相差⾮常⼤，这种效率上的差距的影响往往⽐硬件和软件⽅⾯的差距还要⼤。3、如何选择算法第⼀⾸先要保证算法的正确性⼀个算法对其每⼀个输⼊的实例，都能输出正确的结果并停⽌，则称它是正确的，我们说⼀个正确的算法解决了给定的计算问题。不正确的算法对于某些输⼊来说，可能根本不会停⽌，或者停⽌时给出的不是预期的结果。然⽽，与⼈们对不正确算法的看法想反，如果这些算法的错误率可以得到控制的话，它们有时候也是有⽤的。但是⼀般⽽⾔，我们还是仅关注正确的算法！第⼆分析算法的时间复杂度算法的时间复杂度反映了程序执⾏时间随输⼊规模增长⽽增长的量级，在很⼤程度上能很好反映出算法的好坏。1、什么是时间复杂度⼀个算法花费的时间与算法中语句的执⾏次数成正⽐例，哪个算法中语句执⾏次数多，它花费时间就多。⼀个算法中的语句执⾏次数称为语句频度或时间频度。记为T(n)。⼀般情况下，算法中基本操作重复执⾏的次数是问题规模n的某个函数,⽤T(n)表⽰,若有某个辅助函数f(n),使得当n趋近于⽆穷⼤时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。2、时间复杂度的计算⽅法⼀个算法执⾏所耗费的时间，从理论上是不能算出来的，必须上机运⾏测试才能知道。但我们不可能也没有必要对每个算法都上机测试因为该⽅法有两个缺陷：想要对设计的算法的运⾏性能进⾏测评，必须先依据算法编写相应的程序并实际运⾏。所得时间的统计计算依赖于计算机的硬件、软件等环境因素，有时候容易掩盖算法的本⾝优势。所以只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且⼀个算法花费的时间与算法中语句的执⾏次数成正⽐例，哪个算法中语句执⾏次数多，它花费时间就多。

⼀般情况下，算法的基本操作重复执⾏的次数是模块n的某⼀个函数f(n),因此，算法的时间复杂度记做：T(n)=O(f(n))。随着模块n的增⼤，算法执⾏的时间的增长率和f(n)的增长率成正⽐，所以f(n)越⼩，算法的时间复杂度越低,算法的效率越⾼。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执⾏次数，再找出T(n)的同数量级(它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平⽅，n的三次⽅，2的n次⽅，n!)，找出后，f(n)=该数量级，若T(n)/f(n)求极限可得到⼀常数c，则时间复杂度T(n)=O(f(n))。3、常见的时间复杂度常见的算法时间复杂度由⼩到⼤依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!) 求解算法的时间复杂度的具体步骤：找出算法中的基本语句，算法中执⾏最多的那条语句是基本语句，通常是最内层循环的循环体。计算基本语句的执⾏次数的量级，保证最⾼次幂正确即可查看他的增长率。⽤⼤O⼏号表⽰算法的时间性能 如果算法中包含镶套的循环，则基本语句通常是最内层的循环体，如果算法中包并列的循环，则将并列的循环时间复杂度相加，例如：#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'n = 100for i in range(n): print(i)for i in range(n): ##每循i⾥的⼀个元素,for循环内部嵌套的for循环就整个循环⼀次 for q in range(n): print(q)第⼀个for循环的时间复杂度为Ο(n)，第⼆个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。Ο(1)表⽰基本语句的执⾏次数是⼀个常数，⼀般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,⽽Ο(2n)和Ο(n!)称为指数时间，计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，⽽把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, ⾮确定多项式）问题。在选择算法的时候，优先选择前者！

OK我懂对于没有算法基础的同学，看起算法来也很头疼，但是这个是基础和重点，不会算法的开发不是⼀个合格的开发并且包括语⾔记得基础也是需要好好整理的！加油吧~~ 咱们在⼀起看下时间复杂度的详细说明吧1、O(1)#O(1)n = 100

sum = (1+n) * n/2 #执⾏⼀次sum_1 = (n/2) - 10 #执⾏⼀次sum_2 = n*4 - 10 + 8 /2 #执⾏⼀次这个算法的运⾏次数函数是f(n)=3。根据我们推导⼤O阶的⽅法，第⼀步就是把常数项3改为1。在保留最⾼阶项时发现，它根本没有最⾼阶项，所以这个算法的时间复杂度为O(1)。并且：如果算法的执⾏时间不随着问题规模n的增长⽽增加，及时算法中有上千条语句，其执⾏的时间也不过是⼀个较⼤的常数。此类算法的时间复杂度记作O(1)2、O(n2)n = 100

for i in range(n): #执⾏了n次 for q in range(n): #执⾏了n2 print(q) #执⾏了n2解：T(n)=2n2+n+1 =O(n2)⼀般情况下，对进循环语句只需考虑循环体中语句的执⾏次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若⼲个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

3、O(n)

#O(n)n =100

a = 0 #执⾏⼀次b = 1#执⾏⼀次for i in range(n): #执⾏n次 s = a +b #执⾏n-1次 b =a #执⾏n-1次 a =s #执⾏n-1次解：T(n)=2+n+3(n-1)=4n-1=O(n)4、Ο(n3)#O(n3)n = 100for i in range(n):#执⾏了n次 for q in range(n):#执⾏了n^2 for e in range(n):#执⾏了n^3 print(e)#执⾏了n^3简单点来去最⼤值是：Ο(n3)5、常⽤的算法的时间复杂度和空间复杂度排序法冒泡排序交换排序选择排序插⼊排序快速排序希尔排序（SHELL）归并排序堆排序平均时间Ο(n2)Ο(n2)Ο(n2)Ο(n2)Ο(nlogn)Ο(log2n)Ο(log2n)Ο(log2n)最差情况Ο(n2)Ο(n2)Ο(n2)Ο(n2)Ο(n2)Ο(ns) 1

基数排序Ο(logRB)Ο(logRB)

排序算法是在更复杂的算法中的是⼀个构建基础，所以先看下常⽤的排序。1、冒泡排序需求：请按照从⼩到⼤对列表，进⾏排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619]

思路：相邻两个值进⾏⽐较，将较⼤的值放在右侧，依次⽐较！原理图：原理分析：列表中有5个元素两两进⾏⽐较，如果左边的值⽐右边的值⼤,就⽤中间值进⾏循环替换！既然这样，我们还可以⽤⼀个循环把上⾯的循环进⾏在次循环，⽤表达式构造出内部循环！代码实现：#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'import randommaopao_list = [13, 22, 6, 99, 11]'''原理分析:列表中有5个元素两两进⾏⽐较，如果左边的值⽐右边的值⼤,就⽤中间值进⾏循环替换！既然这样，我们还可以⽤⼀个循环把上⾯的循环进⾏在次循环，⽤表达式构造出内部循环！'''def handler(array): for i in range(len(array)): for j in range(len(array)-1-i): ''' 这⾥为什么要减1,我们看下如果⾥⾯有5个元素我们需要循环⼏次?最后⼀个值和谁对⽐呢?对吧!所以需要减1 这⾥为什么减i?,这个i是循环的下标,如果我们循环了⼀次之后最后⼀只值已经是最⼤的了还有必要再进⾏⼀次对⽐吗?没有必要~ ''' print('left:%d' % array[j],'right:%d' % array[j+1]) if array[j] > array[j+1]: tmp = array[j] array[j] = array[j+1] array[j+1] = tmpif __name__ == '__main__': handler(maopao_list) print(maopao_list)时间复杂度说明看下他的代码复杂度会随着N的增⼤⽽成指数型增长，并且根据判断他时间复杂度为Ο(n2)2、选择排序需求：请按照从⼩到⼤对列表，进⾏排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 思路：第⼀次，从列表最左边开始元素为array[0]，往右循环，从右边元素中找到⼩于array[0]的元素进⾏交换，直到右边循环完之后。第⼆次，左边第⼀个元素现在是最⼩的了，就从array[1],和剩下的array[1:-1]内进⾏对⽐，依次进⾏对⽐！对⽐：他和冒泡排序的区别就是，冒泡排序是相邻的两两做对⽐，但是选择排序是左侧的“对⽐元素”和右侧的列表内值做对⽐！原理图：代码实现：#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'xuanze_list = [13, 22, 6, 99, 11]print(range(len(xuanze_list)))def handler(array): for i in range(len(array)): ''' 循环整个列表 ''' for j in range(i,len(array)): ''' 这⾥的⼩循环⾥,循环也是整个列表但是他的起始值是i,当这⼀个⼩循环完了之后最前⾯的肯定是已经排序好的 第⼆次的时候这个值是循环的第⼏次的值⽐如第⼆次是1,那么循环的起始值就是array[1] ''' if array[i] > array[j]: temp = array[i] array[i] = array[j] array[j] = temp # print(array)if __name__ == '__main__': handler(xuanze_list) print(xuanze_list)选择排序代码优化：#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'import randomimport timedef handler(array): for i in range(len(array)): smallest_index = i #假设默认第⼀个值最⼩ for j in range(i,len(array)): if array[smallest_index] > array[j]: smallest_index = j #如果找到更⼩的,记录更⼩元素的下标 ''' ⼩的循环结束后在交换,这样整个⼩循环就之前的选择排序来说,少了很多的替换过程,就只替换了⼀次!提升了速度 ''' tmp = array[i] array[i] = array[smallest_index] array[smallest_index] = tmpif __name__ == '__main__': array = [] old_time = () for i in range(50000): (nge(1000000)) handler(array) print(array) print('Cost time is :',() - old_time)3、插⼊排序需求：请按照从⼩到⼤对列表，进⾏排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619]

思路：⼀个列表默认分为左侧为排序好的，我们拿第⼀个元素举例，他左边的全是排序好的，他右侧是没有排序好的，如果右侧的元素⼩于左侧排序好的列表的元素就把他插⼊到合适的位置原理图： 代码实现：#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'import randomimport timechaoru_list = [69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619]def handler(array): for i in range(1,len(array)): position = i #刚开始往左边⾛的第⼀个位置 current_val = array[i] #先把当前值存下来 while position > 0 and current_val < array[position -1]: ''' 这⾥为什么⽤while循环,咱们在判断左边的值得时候知道他有多少个值吗?不知道,所以⽤while循环 什么时候停下来呢?当左边没有值得时候,或者当他⼤于左边的值得时候! ''' array[position] = array[position - 1] #如果whille条件成⽴把当前的值替换为他上⼀个值 ''' ⽐如⼀个列表: [3,2,4,1] 现在循环到 1了,他前⾯的元素已经循环完了 [2,3,4] 1 ⾸先我们记录下当前这个position的值 = 1 [2,3,4,4] 这样,就出⼀个位置了 在对⽐前⾯的3,1⽐3⼩ [2,3,3,4] 在替换⼀下他们的值 在对⽐2 [2,2,3,4] 最后while不执⾏了在进⾏替换'array[position] = current_val #把值替换' ''' position -= 1 #当上⾯的条件都不成⽴的时候{左边没有值/左边的值不⽐⾃⼰的值⼩} array[position] = current_val #把值替换if __name__ == '__main__': handler(chaoru_list) print(chaoru_list)''' array = []#[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] old_time = () for i in range(50000): (nge(1000000)) handler(array) print(array) print('Cost time is :',() - old_time)'''4、快速排序设要排序的数组是A[0]……A[N-1]，⾸先任意选取⼀个数据（通常选⽤数组的第⼀个数）作为关键数据，然后将所有⽐它⼩的数都放到它前⾯，所有⽐它⼤的数都放到它后⾯，这个过程称为⼀趟快速排序。值得注意的是，快速排序不是⼀种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产⽣变动.他的时间复杂度是：O(nlogn) ~Ο(n2)排序⽰例：假设⽤户输⼊了如下数组：创建变量i=0（指向第⼀个数据）[i所在位置红⾊⼩旗⼦], j=5(指向最后⼀个数据)[j所在位置蓝⾊⼩旗⼦], k=6(为第⼀个数据的值)。我们要把所有⽐k⼩的数移动到k的左⾯，所以我们可以开始寻找⽐6⼩的数，从j开始，从右往左找，不断递减变量j的值，我们找到第⼀个下标3的数据⽐6⼩，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第⼀次⽐较：i=0 j=3 k=6接着，开始第⼆次⽐较，这次要变成找⽐k⼤的了，⽽且要从前往后找了。递加变量i，发现下标2的数据是第⼀个⽐k⼤的，于是⽤下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表： i=2 j=3 k=6称上⾯两次⽐较为⼀个循环。接着，再递减变量j，不断重复进⾏上⾯的循环⽐较。在本例中，我们进⾏⼀次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第⼀遍⽐较结束。得到结果如下，凡是k(=6)左边的数都⽐它⼩，凡是k右边的数都⽐它⼤：如果i和j没有碰头的话，就递加i找⼤的，还没有，就再递减j找⼩的，如此反复，不断循环。注意判断和寻找是同时进⾏的。然后，对k两边的数据，再分组分别进⾏上述的过程，直到不能再分组为⽌。注意：第⼀遍快速排序不会直接得到最终结果，只会把⽐k⼤和⽐k⼩的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执⾏此步骤，然后再分解数组，直到数组不能再分解为⽌（只有⼀个数据），才能得到正确结果。代码实现：#!/usr/bin/env python# -*- coding:utf-8 -*-# Author:luotianshuaiimport randomimport timedef quick_sort(array,start,end): if start >= end: return k = array[start] left_flag = start right_flag = end while left_flag < right_flag: ''' left_flag = start 默认为0 right_flag = end 默认为传来的列表总长度 当left_flag ⼩与right_flag的时候成⽴,说明左右两边的⼩旗⼦还没有碰头(为相同的值) ''' #右边旗⼦ while left_flag < right_flag and array[right_flag] > k:#代表要继续往左⼀移动⼩旗⼦ right_flag -= 1 ''' 如果上⾯的循环停⽌说明找到右边⽐左边的值⼩的数了,需要进⾏替换 ''' tmp = array[left_flag] array[left_flag] = array[right_flag] array[right_flag] = tmp #左边旗⼦ while left_flag < right_flag and array[left_flag] <= k: #如果没有找到⽐当前的值⼤的,left_flag 就+=1 left_flag += 1 ''' 如果上⾯的循环停⽌说明找到当前段左边⽐右边⼤的值,进⾏替换 ''' tmp = array[left_flag] array[left_flag] = array[right_flag] array[right_flag] = tmp #进⾏递归把问题分半 quick_sort(array,start,left_flag-1) quick_sort(array,left_flag+1,end)if __name__ == '__main__': array = [] # [69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] start_time = () for i in range(50000): (nge(1000000)) quick_sort(array,0,len(array)-1) end_time = () print(array) print(start_time,end_time) cost_time = end_time - start_time print('Cost time is :%d' % cost_time)