查找、排序算法整理

查找算法分类

查找可分为静态查找和动态查找：

静态查找：仅对查找表做查询和检索操作。
动态查找：在查找时包含插入、删除或修改。

还可分为无序查找和有序查找：

无序查找：被查找数列有序无序均可。
有序查找：被查找数列必须为有序数列。典型的有二分查找、插值查找、斐波那契查找。

排序算法分类

排序包括内部排序和外部排序：

内部排序：整个排序过程不需要访问外存即可完成。
外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

内部排序包括：

插入排序：包括直接插入排序、希尔排序（缩小增量排序）
选择排序：包括简单选择排序、堆排序
交换排序：包括冒泡排序、快速排序
归并排序
基数排序

外部排序包括：

多路归并排序（最常用）：即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。
外分配排序：其原理类似于内排序中的桶排序。在归并排序和桶排序之间存在数学上的某种对偶性。
此外还有一些不耗费附加磁盘空间的原地排序算法。不再过多介绍。

查找和排序总结

以下图片源自：https://blog.****.net/u011552404/article/details/78973058

查找算法

对于查找算法，采用平均查找长度作为衡量标准。

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。其中： 　　
　　Pi：查找表中第i个数据元素的概率。
　　Ci：找到第i个数据元素时已经比较过的次数。

附超全的查找算法详细介绍：https://blog.****.net/sayhello_world/article/details/77200009

排序算法

对于排序算法，采用时间和空间复杂度作为评价标准。

附排序算法详细介绍：https://blog.****.net/hguisu/article/details/7776068