常见算法

1. 查找一个数组的中位数？

   • 基本思路是：任意挑一个元素，以该元素为支点，将数组分成两部分，左部分是小于等于支点的，右部分是大于支点的。如果你的运气爆棚，左部分正好是（n－1）／2个元素，那么支点的那个数就是中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位点。
     这种方法很快，但是在最坏的情况下时间复杂度为O(N^2), 不过平均时间复杂度好像是O(N)。

   • 将前(n+1)/2个元素调整为一个小顶堆，
     对后续的每一个元素，和堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。 如果大于堆顶，用该元素取代堆顶，调整堆，取下一元素。重复2.2步
     当遍历完所有元素之后，堆顶即是中位数。

2. 查找N个元素中的第K个小的元素（来自编程珠玑）

   • 编程珠玑给出了一个时间复杂度O（N），的解决方案。该方案改编自快速排序。
     经过快排的一次划分，
     1）如果左半部份的长度>K-1，那么这个元素就肯定在左半部份了
     2）如果左半部份的长度==K-1，那么当前划分元素就是结果了。
     3）如果。。。。。。。<K-1,那么这个元素就肯定在右半部分了。
     并且，该方法可以用尾递归实现。效率更高。

     时间复杂度分析， 由于差不多每次都是把序列划分为一半。。。假设划分的元素做了随机优化，时间复杂度近似于N+N/2+N/4…. = 2N*(1-2^-(logN)) 当N较大时 约等于 2N 也就是 O（N）。

3. 查找N个元素中的第K个小的元素，假设内存受限，仅能容下K/4个元素。

   • 分趟查找，
     第一趟，用堆方法查找最小的K/4个小的元素，同时记录剩下的N-K/4个元素到外部文件。
     第二趟，用堆方法从第一趟筛选出的N-K/4个元素中查找K/4个小的元素，同时记录剩下的N-K/2个元素到外部文件。
     。。。
     第四趟，用堆方法从第一趟筛选出的N-K/3个元素中查找K/4个小的元素，这是的第K/4小的元素即使所求。