python里有算法吗

了解算法之前，我们先看一下什么是算法

定义：算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

python中的常见算法

冒泡排序

效率：O(n2)

原理：

比较相邻的元素，如果第一个比第二个大，就交换他们两个；

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。做完以后，最后的元素会是数，这里可以理解为走了一趟；

针对所有的元素重复以上的步骤，除了最后一个；

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较，最后数列就是从大到小一次排列；

defbubble_sort(data):
"""
冒泡排序
:paramdata:
:return:
"""
foriinrange(len(data)-1):#趟数
forjinrange(len(data)-i-1):#遍历数据，依次交换
ifdata[j]>data[j+1]:#当较大数在前面
data[j],data[j+1]=data[j+1],data[j]#交换两个数的位置
if__name__=='__main__':
importrandom
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：

defselect_sort(data):
"""
选择排序
:paramdata:待排序的数据列表
:return:
"""
foriinrange(len(data)-1):#趟数
min_index=i#记录i趟开始最小的数的索引，我们从最左边开始
forjinrange(i+1,len(data)):#每一次趟需要循环的次数
ifdata[j]<data[min_index]:#当数列中的某一个数比开始的数要小时候，更新最小值索引位置
min_index=j
data[i],data[min_index]=data[min_index],data[i]#一趟走完，交换最小值的位置，第一趟最小
if__name__=='__main__':
importrandom
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：

definsert_sort(data):
"""
插入排序
:paramdata:待排序的数据列表
:return:
"""
foriinrange(1,len(data)):#无序区域数据
tmp=data[i]#第i次插入的基准数
forjinrange(i,-1,-1):
iftmp<data[j-1]:#j为当前位置，试探j-1位置
data[j]=data[j-1]#移动当前位置
else:#位置确定为j
break
data[j]=tmp#将当前位置数还原
if__name__=='__main__':
importrandom
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直到某一指针达到序列尾；