★经典问题—元素选择问题

元素选择问题 : 给定线性序集中n个元素和一个整数k(1<=k<=n)，要求找出这n个元素中第k小的元素(第n-k大)。这一问题可以演化成找最大最小值、找中位数等。

最简单思想：如果是直接找最大最小值，则可以通过N次比较来完成，其时间复杂度为O(N)，空间复杂度为O(1)。除此之外，对于一般的k值，可以考虑对序列N先进行排序，然后直接定位第k个位置上的数即可。时间复杂度最好为O(N*logN)。

改进思想：

(1) 在某些特殊情况下，是很容易设计出O(N)的算法。比如最大最小值的时候。

如果k<=n/logn 找第k小的元素。我们可以通过堆排序的方法。首先建立小顶堆，其时间复杂度为O(N)。然后每次输出堆顶元素(当前堆的最小值)后调整堆顶，其时间复杂度为O(logN)。循环k次，当第k次输出堆顶时结束。这样的时间复杂度为O(N+k*logN), 而k<=n/logn，即k接近于常数，则时间复杂度近似为O(N)。

如果k>=n-n/logn 找第k小的元素。同理可以建立一个(n-k)次输出的大顶堆即可。

当k的大小靠近n的两侧时，比如n=10，k=2或8。我们可以同归堆排序来达到近似O(N)的时间复杂度。

(2) 但一般的k值，特别是中位数的选择问题似乎就比上一种情况要难了。但事实上，我们仍然可以在O(n)的时间内解决。

可以考虑快排的分治算法，对N序列进行一次Partition。与快排不同的是，每次只对划分后的一个子数组进行处理。其算法代码如下：

Cpp代码

1. //在a数组中选择第k小的数
2. Type select(Type a[], int low, int high, int k){
3. //找到的第k小的数
4. if(low==high) return a[low];
5. //一次选择划分，此时a[low..mid-1]<a[mid]<a[mid+1..high]
6. int mid=partition(a,low, high);
7. int midSize=mid-low+1;
8. if(k<=midSize) return select(a, low, mid, k);
9. else return select(a, mid+1, high, k-midSize);
10. }

//在a数组中选择第k小的数Type select(Type a[], int low, int high, int k){       //找到的第k小的数       if(low==high) return a[low];       //一次选择划分，此时a[low..mid-1]<a[mid]<a[mid+1..high]       int mid=partition(a,low, high);       int midSize=mid-low+1;       if(k<=midSize) return select(a, low, mid, k);       else return select(a, mid+1, high, k-midSize);}

从代码中很容易看出，在最坏情况下，这种算法和快排有着一样的蜕化现象，需要O(N^2)时间复杂度。但是在一般情况下，平均性能上可以保证近似O(N)的时间复杂度。如果想要克服最坏情况，其基准(快排中的枢轴)的选择可以进行优化。使得基准所划分出来的两个子数组的长度至少为原数组长度的x倍(0<x<1)。具体优化策略可以参见《【JDK优化策略】java.util.Arrays的排序研究》中的快排优化。