系列文章目录

前言

笔记来源于视频（侵删）：

清华计算机博士带你学习Python算法+数据结构

一、查找

在这里插入图片描述

二分查找要求列表有序

二、排序

在这里插入图片描述

总结：

冒号排序：遍历n-1趟，每次两两交换，原地排序。外层循环为for i in range(len(li))，内层循环为for j in range(len(li)-1-i)。可以通过加一个判断（如果这一趟中没有发生交换，则说明已经全部排好序，终止循环）进行优化
选择排序：遍历一遍列表，选择最小的值，放到新列表中，遍历n遍。
插入排序：假定手里的牌已经有序，然后插入。即从第二个数开始遍历n-1趟，每次将当前的数与前面已经排好的数进行比较，将其插入到合适的位置。外层循环为for i in range(1，len(li))，令j=i-1，则内层循环为while tmp<li[j] and j >=0，即当升序排列时，当当前数tmp小于前一个数的时候就把前一个数往后挪，即令li[j] = li[j-1]，j =j-1
快排：选择第一个数tmp，使其左边的数小于tmp，右边的数大于tmp。参数为left、right、li：先往前从right开始遍历找到比tmp小的数，把它放到li[left]位置上，因为将第一个数tmp取出后左边有空位；然后在从left开始往后遍历，找到比tmp大的数，把它放到li[right]上，因为之前取出了right位置上的数，所以有空位，做循环，最后把tmp归位即可。然后做递归，左右两边分别递归，每次循环问题减半。
堆排序：
归并排序：假设两边分别有序，把两边合到一起使其整体有序。参数为low，mid，high，li：令i=low，j=mid+1，tmp=[]，当升序排列时，当左右两边都有数的时候：依次比较li[i]和li[j]的大小，选择小的一个添加到tmp列表中去；当只有一端有数的时候，直接将剩下的数全部添加到tmp列表后面去，因为剩下的数是有序且大于之前添加的数的。然后做递归：当low<high，即最少有两个数的时候，先求出中间值mid，然后左右分别做递归，递归之后再对最小层的数做排序。

插入排序：
在这里插入图片描述

快排：
在这里插入图片描述
堆排序：

在这里插入图片描述

在这里插入图片描述

时间复杂度：

O(1)：执行一次基本操作的时间（近似），1是指1个单位（不看到底执行了几次，只要不上升到n次的时候就是O（1））
O(n^2)：当是n的(2+n)次方时，只保留大的即可，只需大概的时间即可，不需要很精确。
O(logn)：当出现循环减半时，（即每次迭代让问题规模缩小一半）

在这里插入图片描述

时间比空间重要。

1、冒号排序

需要n-1趟排序
在这里插入图片描述

在这里插入图片描述

2、选择排序

遍历一遍列表，选择最小的值，放到新列表中，遍历n遍。

在这里插入图片描述
缺点：

占用了两倍内存，不是原地排序（冒号排序是原地排序），
时间复杂度为O(n^2)
min函数的时间复杂度为O(n)（因为找列表最小值时，需要遍历列表，所以时间复杂度不是O(1)），remove函数的时间复杂度也是O(n)（因为删除列表中的某个数字后，需要将后面的数字依次往前移一位，否则会造成一个空位），所以整个算法的时间复杂度为O(n^2)（循环里面的两个O(n）记为一个）

优化：时间复杂度O(n^2)

在这里插入图片描述