查找

列表查找（线性表查找）

从列表中查找指定元素

• 顺序查找（线性查找）
  从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。
  时间复杂度：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 表示数字位数