焦作做网站/外呼系统电销

以下代码可以从数组a[]中找出第k小的元素。

它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。

请仔细阅读分析源码，填写划线部分缺失的内容。

#include <stdio.h>int quick_select(int a[], int l, int r, int k) {int p = rand() % (r - l + 1) + l;int x = a[p];//随机选择主元{int t = a[p]; a[p] = a[r]; a[r] = t;}int i = l, j = r;while(i < j) {while(i < j && a[i] < x) i++;if(i < j) {a[j] = a[i];j--;}while(i < j && a[j] > x) j--;if(i < j) {a[i] = a[j];i++;}}a[i] = x;p = i;if(i - l + 1 == k) return a[i];if(i - l + 1 < k) return quick_select( _____________________________ ); //填空else return quick_select(a, l, i - 1, k);
}int main()
{int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};printf("%d\n", quick_select(a, 0, 14, 5));return 0;
}

注意：只填写划线部分缺少的代码，不要抄写已经存在的代码或符号。

答案：return quick_select(a, i + 1, r, k- (i - l + 1))

思路：在快排的基础上，寻找第k大的数。

程序理解——

1，随机寻找主元；

2，通过two pointers获得主元的最终位置p，则主元p位置上是M（数值为：p-left +1）大的数

3，用M与k进行比较

3.1，如果相等，则主元就是要寻找的第k大的数，返回

3.2，如果p小于k，则从[left～p-1]的范围里继续寻找第k大的数

3.3 如果p大于k，则从[p+1～right]的范围里继续寻找第k-M大的数（因为区间被划分后，范围减小了，起始位置变为p+1，而p+1为M+1大的数，因此k需要减去M）

参考代码：

#include <stdio.h>
#include <cstdlib>int quick_select(int a[], int l, int r, int k) {int p = rand() % (r - l + 1) + l;int x = a[p];{int t = a[p]; a[p] = a[r]; a[r] = t;}int i = l, j = r;while(i < j) {while(i < j && a[i] < x) i++;if(i < j) {a[j] = a[i];j--;}while(i < j && a[j] > x) j--;if(i < j) {a[i] = a[j];i++;}}a[i] = x;p = i;             //划分后的主元位置if(i - l + 1 == k)//设M=i-l+1是[left，right]中第M小的数return a[i];if(i - l + 1 < k)//如果比主元大，则从主元后面的数去寻找，第k-M小的数//return quick_select( _____________________________ ); //填空return quick_select(a, i + 1, r, k- (i - l + 1));else                //往主元左侧寻找第K小的数return quick_select(a, l, i - 1, k);
}int main()
{int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};//int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};printf("%d\n", quick_select(a, 0, 14, 7));return 0;
}