1.实践题目名称：
找第k小的数
2.问题描述：
设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。
3.算法描述：
定义一个分割函数，实现返回指定数组中的数在数组中是第k大的数值k，若该k值与题目所需不符，则传入另一查找函数，在该查找函数中实现在数组的[0,k)或(k,n]段中查找符合要求的k值。函数具体实现如下：
//分割函数
//选取数组中的第一个数作为基数，将数组分成两部分
int partition(int a[],int left,int right){
int i=left+1;
int j=right;
while(i<j){
while(i<right&&a[i]<a[left]) i++;
while(a[j]>a[left]) j--;
if(i>=j) break;
swap(a[i],a[j]);
}
swap(a[j],a[left]);
return j;
}
//查找函数
int find(int a[],int left,int right,int k){
int t=partition(a,left,right);
//递归终止条件
if(t==k-1) return a[t];
//如果基底数经partition返回的下标比k小，则在数组左边查找
else if(t>k-1) find(a,left,t-1,k);
//否则在数组右边进行查找
else find(a,t+1,right,k);
}
4.算法时间及空间复杂度分析：
时间复杂度：每次迭代尽可能遍历数组的一半，故时间复杂度为O(n/2) + O(n/4) + O(n/8) + ... +O(1) = O(n)
空间复杂度：整个过程仅需为数组申请一次空间，故空间复杂度同样为O(n)
5.心得体会：
这次实践使得我对分治法有了更为深刻的理解，以及了解到解决实例的正确思路的思考的重要性。
原文：https://www.cnblogs.com/lgrdeboke/p/13765895.html