了解算法之前,我们先看一下什么是算法
定义:算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
python中的常见算法
冒泡排序
效率:O(n2)
原理:
比较相邻的元素,如果第一个比第二个大,就交换他们两个;
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。做完以后,最后的元素会是最大的数,这里可以理解为走了一趟;
针对所有的元素重复以上的步骤,除了最后一个;
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较,最后数列就是从大到小一次排列;
def bubble_sort(data): """ 冒泡排序 :param data: :return: """ for i in range(len(data)-1): # 趟数 for j in range(len(data)-i-1): # 遍历数据,依次交换 if data[j]>data[j+1]: # 当较大数在前面 data[j],data[j+1]=data[j+1],data[j] #交换两个数的位置 if __name__=='__main__': import random data_list=list(range(30)) random.shuffle(data_list) print("pre:",data_list) bubble_sort(data_list) print("after:",data_list) #结果: #pre: [22, 11, 19, 16, 12, 18, 20, 28, 27, 4, 21, 10, 9, 7, 1, 6, 5, 29, 8, 0, 17, 26, 13, 14, 15, 24, 25, 23, 3, 2] #after: [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, 25, 26, 27, 28, 29]
选择排序
效率:O(n2)
原理:
每一次从待排序的列表中选出一个元素,并将其与其他数依次比较,若列表中的某个数比选中的数小,则交换位置,把所有数比较完毕,则会选出最小的数,将其放在最左边(这一过程称为一趟);
重复以上步骤,直到全部待排序的数据元素排完;
demo:
def select_sort(data): """ 选择排序 :param data: 待排序的数据列表 :return: """ for i in range(len(data)-1): #趟数 min_index=i # 记录i趟开始最小的数的索引,我们从最左边开始 for j in range(i+1,len(data)): # 每一次趟需要循环的次数 if data[j] < data[min_index]: # 当数列中的某一个数比开始的数要小时候,更新最小值索引位置 min_index=j data[i],data[min_index]=data[min_index],data[i] # 一趟走完,交换最小值的位置,第一趟最小 if __name__=='__main__': import random data_list=list(range(30)) random.shuffle(data_list) # 打乱列表数据 print("pre:",data_list) select_sort(data_list) print("after:",data_list) #结果: #pre: [20, 11, 22, 0, 18, 21, 14, 19, 7, 23, 27, 29, 24, 4, 17, 15, 5, 10, 26, 13, 25, 1, 8, 16, 3, 9, 2, 28, 12, 6] #after: [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, 25, 26, 27, 28, 29]
插入排序
效率:O(n2)
原理:
以从小到大排序为例,元素0为第一个元素,插入排序是从元素1开始,尽可能插到前面。
插入时分插入位置和试探位置,元素i的初始插入位置为i,试探位置为i-1,在插入元素i时,依次与i-1,i-2······元素比较,如果被试探位置的元素比插入元素大,那么被试探元素后移一位,元素i插入位置前移1位,直到被试探元素小于插入元素或者插入元素位于第一位。
重复上述步骤,最后完成排序
demo:
def insert_sort(data): """ 插入排序 :param data: 待排序的数据列表 :return: """ for i in range(1, len(data)): # 无序区域数据 tmp = data[i] # 第i次插入的基准数 for j in range(i, -1, -1): if tmp < data[j - 1]: # j为当前位置,试探j-1位置 data[j] = data[j - 1] # 移动当前位置 else: # 位置确定为j break data[j] = tmp # 将当前位置数还原 if __name__=='__main__': import random data_list=list(range(30)) random.shuffle(data_list) # 打乱列表数据 print("pre:",data_list) insert_sort(data_list) print("after:",data_list) #结果: #pre: [7, 17, 10, 16, 23, 24, 13, 11, 2, 5, 15, 29, 27, 18, 4, 19, 1, 9, 3, 21, 0, 14, 12, 25, 22, 28, 20, 6, 26, 8] #after: [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, 25, 26, 27, 28, 29]
堆排序
堆定义:本质是一个完全二叉树,如果根节点的值是所有节点的最小值称为小根堆,如果根节点的值是所有节点的最大值,称为大根堆。
效率:O(nlogn)
原理:
将待排序数据列表建立成堆结构(建立堆);
通过上浮(shift_up)或下沉(shift_down)等操作得到堆顶元素为最大元素(已大根堆为例);
去掉堆顶元素,将最后的一个元素放到堆顶,重新调整堆,再次使得堆顶元素为最大元素(相比第一次为第二大元素);
重复3操作,直到堆为空,最后完成排序;
归并排序
效率:O(nlogn)
空间复杂度:O(n)
原理:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
重复步骤3直到某一指针达到序列尾;
将另一序列剩下的所有元素直接复制到合并序列尾。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]