Python 是一门更注重可读性和效率的语言

正是由于 Python 易于上手这一事实，让有些人没有意识到 Python 也应该是一项必要的编程技能。

下面给大家介绍一下Python-算法

算法基础1.定义

算法(Algorithm )是一个有穷规则(或语句、指令）的有序集合。它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。

数据的逻辑结构与存储结构密切相关:

算法设计:取决于选定的逻辑结构算法实现:依赖于采用的存储结构

​

​​​​

2.算法的特性有穷性——算法执行的步骤（或规则)是有限的;确定性——每个计算步骤无二义性;可行性——每个计算步骤能够在有限的时间内完成;输入，输出——存在数据的输入和出输出3.评价算法好坏的方法正确性：运行正确是一个算法的前提。可读性：容易理解、容易编程和调试、容易维护。健壮性:考虑情况全面，不容以出现运行错误。时间效率高：算法消耗的时间少。储存量低：占用较少的存储空间。时间复杂度计算

算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量。“O"表示一个数量级的概念。根据算法中语句执行的最大次数（频度)来估算一个算法执行时间的数量级。

计算方法：

写出程序中所有运算语句执行的次数，进行加和

如果得到的结果是常量则时间复杂度为1

如果得到的结果中存在变量n则取n的最高次幂作为时间复杂度

下图表示随问题规模n的增大，算法执行时间的增长率。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-p7zGEMZS-1620974836170)(D:\自律\markdown笔记\image-20210513103118699.png)]

排序和查找排序

排序(Sort)是将无序的记录序列(或称文件）调整成有序的序列。

常见排序方法︰

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

def bubbleSort(arr):    for i in range(1, len(arr)):        for j in range(0, len(arr)-i):            if arr[j] > arr[j+1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]    return arr123456

工作原理为，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

def selectionSort(arr):    for i in range(len(arr) - 1):        # 记录最小数的索引        minIndex = i        for j in range(i + 1, len(arr)):            if arr[j] < arr[minIndex]:                minIndex = j        # i 不是最小数时，将 i 和最小数进行交换        if i != minIndex:            arr[i], arr[minIndex] = arr[minIndex], arr[i]    return arr1234567891011

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

def insertionSort(arr):    for i in range(len(arr)):        preIndex = i-1        current = arr[i]        while preIndex >= 0 and arr[preIndex] > current:            arr[preIndex+1] = arr[preIndex]            preIndex-=1        arr[preIndex+1] = current    return arr123456789

步骤:

从数列中挑出一个元素，称为"基准" ( pivot ) ,

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区( partition )操作。

递归地 ( recursive )把小于基准值元素的子数列和大于基准值元素的子数列排序。

def quickSort(arr, left=None, right=None):    left = 0 if not isinstance(left,(int, float)) else left    right = len(arr)-1 if not isinstance(right,(int, float)) else right    if left < right:        partitionIndex = partition(arr, left, right)        quickSort(arr, left, partitionIndex-1)        quickSort(arr, partitionIndex+1, right)    return arrdef partition(arr, left, right):    pivot = left    index = pivot+1    i = index    while  i <= right:        if arr[i] < arr[pivot]:            swap(arr, i, index)            index+=1        i+=1    swap(arr,pivot,index-1)    return index-1def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]1234567891011121314151617181920212223