1.实践题目名称：找第k小的数。
2.问题描述：设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。
3.算法描述：由函数int partition(int a[],int left,int right)、int find(int a[],int left,int right,int k) 和 int main() 构成。
（1）函数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 partition(int a[],int left,int right){
将最左边的数值赋给x;
while(left<right){
while下标为right的数值大于或等于x且left小于right
right左移;
交换下标为left和right的数值;
while下标为left的数值小于于或等于x且left小于right
left右移;
交换下标为left和right的数值;
}
重新赋值x;
返回left;
（2）函数int find(int a[],int left,int right,int k)，通过调用partition函数获得划分点，判断划分点是否第k小，若不是，递归调用find函数继续在左段或右段查找。
int find(int a[],int left,int right,int k){
调用partition函数，将其值赋值给变量p;
如果k-1等于p，输出数组a中下标为k-1的数值;
如果k-1小于p，递归调用find在（left,p-1）区间继续找;
如果k-1大于p，递归调用find在（p+1,right）区间继续找;
return 0;
}
（3）main函数。
int main(){
定义变量n,k;
输入n,k的值;
定义一个大小为1000的数组;
用for循环依次输入数组a;
调用find函数在（n-1,k）区间找数组a中第k大的数;
return 0;
}
4.算法时间及空间复杂度分析（要有分析过程）：
时间复杂度：拿到这道题，我第一时间想到的方法就是直接排序然后输出第k小的数。但是题目要求设计一个平均时间为O(n)的算法，而第一个方法的时间复杂度不符合题目要求，所以并不可行。因此还是要运用学过的分治法和快速排序法。先用数组中的元素x对数组进行划分，分成左右两个区域，然后判断x是否为题目要求的第k小的数，若是，则输出，若不是则继续划分查找，以此类推，直到找到为止。这样就能达到题目要求的平均时间O(n)了。
空间复杂度：find函数中运用了递归，所以空间复杂度应为O(log n)。
5.心得体会（对本次实践收获及疑惑进行总结）
本次上机实践学会了用函数partition（）对数组进行划分，相比于以往较为简单粗暴的直接排序然后输出的算法，更加的巧妙和高级。这一次在题目的要求之下学会了如何区运用更加精巧和高效率的算法去同一个解决问题。上机实践过程中前期对find函数的设计和快速排序算法不太理解，编程进度有点被卡住。在实践结束后，对函数的递归调用，分治法的思想以及数组区域的划分有了更深的了解和认识。
原文：https://www.cnblogs.com/CJJ010725/p/13762572.html