查找
列表查找(线性表查找)
从列表中查找指定元素
-
顺序查找(线性查找)
从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后一个元素为止。
时间复杂度:O(n)
enumerate()函数
range 函数 -
折半查找(二分查找)
从有序列表的初始候选区 li[0:n]开始,通过对待查找的值与候选区中间值 比较,可以使候选区减少一半。
时间复杂度:O(logn) -
插值查找
基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。 -
斐波那契查找(0.618)
基本思想:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。 -
分块查找
将 n 个数据元素"按块有序"划分为 m 块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第 1 块中任一元素的 关键字都必须小于第 2 块中任一元素的关键字;而第 2 块中任一元素又都必须小于第 3 块中的任一元素 -
哈希查找
如果所有的键都是整数,可以使用一个简单的无序数组,将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键 >“空间换时间”
排序
列表排序
将无序列表变为有序列表
升序:小到大;降序:大到小
-
冒泡排序
列表每两个相邻的数,如果前面比后面大,则交换这两个数。
一趟排序完成后,则无序区减少一个属,有序区增加一个数。
一趟冒泡排序完成后,最大的数排在了列表的最后
时间复杂度:O(n^2) -
选择排序
在要排序的一组数中,选出最小(或者最大)的一个数与第 1 个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第 2 个位置的数交换,依次类推,直到第 n-1 个元素(倒数第二个数)和第 n 个元素(最后一个数)比较为止。
时间复杂度 O(n^2) -
插入排序
在待排序的元素中,假设前 n-1 个元素已有序,现将第 n 个元素插入到前面已经排好的序列中,使得前 n 个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
时间复杂度 O(n^2) -
快速排序
取一个元素 p(第一个元素),使元素 p 归位,列表被 p 分成两部分,左边都比 p 小,右边都比 p 大,递归完成排序
时间复杂度:O(nlogn) -
堆排序
1.建立堆(构造堆)
2.得到堆顶元素,为最大元素
3.去掉堆顶,将堆最后一个元素放到堆顶,此时可以通过一次向下调整使堆有序
4.堆顶元素为第二大元素
5.重复步骤 3,直到堆变空
时间复杂度:O(nlogn) -
归并排序
归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列。
步骤:
1.分解:将列表越分越小,直到分成一个元素
2.终止条件:一个元素是有序的
3.合并:将两个有序列表归并,列表越来越大
时间复杂度:O(nlogn),空间复杂度:O(n)python 内部排序 sort,基于归并排序和插入排序。
-
希尔排序
一种分组插入排序算法
思路:
先选定一个整数 d1=n/2 作为第一增量,然后将所有距离为 d1 的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个第二增量 d2=d1/2,重复上述操作。当 di 的大小减到 1 时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。时间复杂度与选取的 gap 有关,一般小于 O(n^2)
-
计数排序
计数排序是一种非比较排序,其核心是将序列中的元素作为键存储在额外的数组空间中,而该元素的个数作为值存储在数组空间中,通过遍历该数组排序。
条件: 已知列表范围 -
桶排序
特殊的计数排序
将元素分在不同的桶中,在对每个桶中的元素排序
桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采用不同的分桶策略
平均时间复杂度:O(n+k),最坏情况:O(n^2k)。空间复杂度:O(nk) -
基数排序
排序算法是一种非比较算法,其原理是将整数按每个位数分别比较。它利用了桶的思想。时间复杂度:O(kn),空间复杂度:O(k+n)。k 表示数字位数