算法：O(n)时间内在数组中找到第k个小的数

从一个长度为n的无序数组中，找到第k小的那个数，被称为k-select问题。我们经常见到的问题：找到中位数，找到第二个大的数，都是这个问题的特例。

算法的复杂度是O(20n），当选择为5个数为一个小集合时。

OJ风格的完整代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

#define Q 5
#define LOCAL

int A[1001];
int n;
int k;


int cmp(const void *a, const void *b) {
	return *(int *)a - *(int *)b;
}

int trivivalSelect(int *A, int n, int k) {
	int temp[1001];
	memset(temp, 0, sizeof(int)*1001);
	memmove(temp, A, sizeof(int)*n);
	qsort(temp, n, sizeof(int), cmp);
	printf("trivivalSelect: %d\n", temp[k]);
	return temp[k];
}


int kselect(int* A, int n, int k) {
	if (n < Q) {
		return trivivalSelect(A, n, k);
	}
	int mid[1001];
	int temp[1001];
	memset(mid, 0, sizeof(int)*1001);


	
	int i = 0;
	int c = 0;
	while (i < n) {
		int count = (n - i < Q ? n - i : Q);
		memset(temp, 0, sizeof(int)*1001);
		memmove(temp, A + i, sizeof(int)*count);
		qsort(temp, count, sizeof(int), cmp);
		mid[c++] = temp[count / 2];
		i += count;
	}
	printf("mid: ");
	for (i = 0; i < c; i++) {
		printf("%d ", mid[i]);
	}
	printf("\n");
	int M_mid = kselect(mid, c, c/2);
	int L[1001];
	int E[1001];
	int G[1001];
	memset(L, 0, sizeof(int)*1001);
	memset(E, 0, sizeof(int) * 1001);
	memset(G, 0, sizeof(int) * 1001);
	int l = 0;
	int e = 0;
	int g = 0;
	for (int i = 0; i < n; i++) {
		if (A[i] < M_mid)
			L[l++] = A[i];
		else if (A[i] == M_mid)
			E[e++] = A[i];
		else
			G[g++] = A[i];
	}
	printf("l: %d e: %d g: %d k: %d\n", l, e, g,k);
	assert(l + g + e == n);
	if (l >= k+1)
		return kselect(L, l, k);
	else if (l + e >= k+1)
		return M_mid;
	else
		return kselect(G, g, k - l - e);
}

int main() {
#ifdef LOCAL
	freopen("data.in", "r", stdin);
	freopen("data.out", "w", stdout);
#endif
	memset(A, 0, sizeof(int)*1001);
	scanf("%d %d\n", &n, &k);
	if (k < 0 || k >= n) {
		printf("INVALID\n");
		return 0;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d\n", &A[i]);
	}
	int M;
	M = kselect(A, n, k);
	printf("%d\n", M);
	qsort(A, n, sizeof(int),cmp);
	printf("%d",A[k]);
	return 0;
}

代码中除了printf("%d\n",M)外，所有printf代码都是调试信息，应该删去。

代码从文件中读取输入，重定向到stdin，然后使用scanf读取，第一行是两个数，用空格隔开，分别为输入数组的大小n和要求的位置k（最小的那个数，k就是0，中位数就是n/2下取整），接下来是n行，每行一个数。

代码输出到stdout，重定向到文件，输出为一个数，即第k小的那个数。