十大经典排序算法&七大查找算法

十大经典排序算法：

十大经典排序算法

    十大经典排序算法的时间、空间复杂度：

复杂度

冒泡排序（Bubble Sort）

算法描述 ：

1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3、针对所有的元素重复以上的步骤，除了最后一个；

重复步骤1~3，直到排序完成。

选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理：在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 

插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并。 

快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述：

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1、从数列中挑出一个元素，称为 “基准”（pivot）；

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

3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

---

七大查找算法

[1. 顺序查找]：顺序查找适合于存储结构为顺序存储或链接存储的线性表。时间复杂度为O(n)。

[2. 二分查找]：属于有序查找算法，元素必须是有序的，如果是无序的则要先进行排序操作。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。时间复杂度为O(log2n)

[3. 插值查找]：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。时间复杂度均为O(log2(log2n))

[4. 斐波那契查找]：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。最坏情况下，时间复杂度为O(log2n)

[5. 树表查找]：包括二叉树查找法、平衡查找树、红黑树、B树和B+树

[6. 分块查找]：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

[7. 哈希查找]：哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。