查找不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。 二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

排序算法可以说是一项基本功，解决实际问题中经常遇到，针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率，有时候排序的稳定性还是实际问题中必须考虑的，这篇博客对常见的排序算法进行整理，包括：选择排序、插入排序、希尔排序、冒泡排序、鸡尾酒排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序(代码略)。

前面讨论的排序算法，都假定要排序的所有数据在内存中都同时可用，如数组。要对存储在外部文件中的数据排序，首先要将数据送入内存，然后对它们进行内部排序。然而，如果文件太大，那么文件中的所有数据不能都同时送入内存。在大型外部文件中对数据排序，称为外部排序(external sort)。

堆排序是把数组看作堆，第i个结点的孩子结点为第 2i + 1和 2i + 2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。

假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标i)，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。 然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。

无论是冒泡排序，还是快速排序等等，都是基于元素之间的比较来进行排序。有一种特殊的算法叫做 计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

快速排序的基本思想：通过一趟排序将待排数列分隔成独立的两部分，其中一部分数列的关键字均比另一部分的关键字小，则可分别对这两部分数列继续进行排序，以达到整个序列有序。 其中，最重要的partition主要有两种方法： 1)指针交换法。先把选定为pivot的元素放到最后，然后设定指针low和指针high，low指针右移，high指针左移，当两个指针相撞后停止移动。期间如果符合交换条件，两元素交换。最后把pivot元素放到中间。 2)挖坑法。类似冒泡排序的思路，把比pivot大的元素“往下沉”，把比pivot小的元素“往上浮”。

归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度，代价是需要额外的内存空间。 归并排序算法将数组每一次都分解为原来的一半大小的两个子数组，当分解到了右边界比左边界还大的时候，不再分解，开始排序。 然后将排序好的子数组逐级合并，最后得到的结果就是排序好的数组。