线性时间选择(TOP K)

问题描述：

找出一个数组中第K小的元素，时间复杂度为O(n)。

解法：

1.首先大家都会想到的解法是排序，之后找出第k个元素，但是排序的时间复杂度不符合要求，或者需要额外的空间。

2.利用快排的思想，以枢纽（随机得到）为界，将数组分为2部分，一部分小于等于这个枢纽值，一部分大于这个枢纽值，与快排不同的是，我们只处理一部分，另一部分舍弃。

代码如下：

#include<iostream> #include<algorithm> #include<time.h> #include<cstring> #define random(x) (rand()%x) //生成随机数用的using namespace std;//交换两个数的值void swap(int arr[], int i, int j) {int tem;tem = arr[i];arr[i] = arr[j];arr[j] = tem;}int partition(int arr[], int L, int R) {int less = L - 1;int more = R;while (L < more) {if (arr[L] < arr[R]) {swap(arr, ++less, L++);}else if (arr[L] > arr[R]) {swap(arr, --more, L);}else {L++;}}swap(arr, more, R);//将枢纽从最后的位置移动到分界处int p = more;return p; //返回枢纽的位置}int quicksort_select(int arr[], int L, int R,int k) {srand((int)time(0));//种子，为了每次生成的随机数不同if (k > (R - L + 1) || k < 1) {return -1;}int P;if (L < R) {swap(arr, L + (int)(random(1000) / (float)(1000)*(R - L + 1)), R); //生成一个随机数，再把随机数所在位置的数与数组最后一个数交换P = partition(arr, L, R);}int j = P - L + 1;if (j == k) {return arr[P];}else if (j>k) {quicksort_select(arr, L, P, k);}else {quicksort_select(arr, P + 1, R, k - j);}}int main() {//textint a[5] = { 1,2,3,4,5 };int m=quicksort_select(a, 0, 4, 2);cout << m;}

代码分析如下：

partition函数返回枢纽的坐标P，P-L+1是左半部分元素的个数，这部分的元素都小于等于枢纽的值，右半部分的元素值都大于枢纽的值，如果j<P-L+1说明第j个小的元素，在左半部分，让后只需要递归的处理左半部分即可，如果P等于j，那么很幸运，枢纽的值就是我们的所求，如果j>P-L+1，说明第k个小的元素在右半部分，指的注意的是，我们所求的数是右半部分第j-(P-L+1)小的数，我们这时候处理右半部分即可。这种方法在平均的时间复杂度是O(n)（证明看《算法导论》），但他有一个额外的产生随机数，这个的效率据说很低（没有亲自探测）；

3.采用中位数线性时间选择，我放到下一篇文章。