中财网葡萄什么时候埋土:★经典问题—元素选择问题
来源：百度文库 编辑：中财网 时间：2024/04/29 08:06:19
元素选择问题 : 给定线性序集中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代码- //在a数组中选择第k小的数
- Type select(Type a[], int low, int high, int k){
- //找到的第k小的数
- if(low==high) return a[low];
- //一次选择划分，此时a[low..mid-1]
- 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);
- }
//在a数组中选择第k小的数Type select(Type a[], int low, int high, int k){ //找到的第k小的数 if(low==high) return a[low]; //一次选择划分，此时a[low..mid-1]从代码中很容易看出，在最坏情况下，这种算法和快排有着一样的蜕化现象，需要O(N^2)时间复杂度。但是在一般情况下，平均性能上可以保证近似O(N)的时间复杂度。如果想要克服最坏情况，其基准(快排中的枢轴)的选择可以进行优化。使得基准所划分出来的两个子数组的长度至少为原数组长度的x倍(0