设计一个平均时间为o(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。 提示：函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x（如a[left])对a[left]~a[right]进行划分，划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int right,int k)函数，通过调用partition函数获得划分点，判断划分点是否第k小，若不是，递归调用find函数继续在左段或右段查找。

这道题要求我们设计一个时间复杂度为O(n)的算法，在n个无序的整数中找出第k小的数。

我们可以利用快速排序中的partition函数来解决这个问题。具体来说，我们可以编写一个find函数，该函数的参数包括一个整数数组a，以及数组的左右边界left和right，还有要查找的第k小的数。

在find函数中，我们可以调用partition函数，将数组a[left]~a[right]划分为两个部分，左边部分的数都小于等于a[left]，右边部分的数都大于等于a[left]。同时，我们可以利用partition函数返回的划分点的位置pos，来判断a[pos]是否是第k小的数。如果是，我们就直接返回a[pos]；如果不是，我们就递归调用find函数，在左边或右边部分继续查找第k小的数。

具体的实现细节可以参考下面的代码：

int partition(int a[], int left, int right) {
int pivot = a[left];
int i = left, j = right;
while (i < j) {
while (i < j && a[j] >= pivot) j--;
a[i] = a[j];
while (i < j && a[i] <= pivot) i++;
a[j] = a[i];
}
a[i] = pivot;
return i;
}

int find(int a[], int left, int right, int k) {
int pos = partition(a, left, right);
if (pos == k - 1) {
return a[pos];
} else if (pos > k - 1) {
return find(a, left, pos - 1, k);
} else {
return find(a, pos + 1, right, k);
}
}

int main() {
int n, k;
int a[100];
cin >> n >> k;
for (int i = ; i < n; i++) {
cin >> a[i];
}
int ans = find(a, , n - 1, k);
cout << ans << endl;
return ;
}