python中有算法吗

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

定义

：算法（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)

原理：

每次从列表中选择一个元素进行排序，依次与其他数字进行比较。如果列表中有一个数比选中的数小，交换位置，比较所有的数，选出最小的，放在最左边（这个过程称为pass）；

重复上述步骤，直到所有需要排序的数据元素都被排完为止；

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的插入位置向前移动一位，直到被测元素小于插入元素或插入的元素在第一个位置。

重复上述步骤，最后完成排序

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直到某一指针达到序列尾；

将另一个序列的所有剩余元素直接复制到合并序列的末尾。