1、实践题目
找第k小的数
2、问题描述
在n个(1<=n<=1000)个整数中找到第k小的数，并且平均时间复杂度为O（n)。
3、算法描述
partition：选择第一个数x为基准数，将数组中小于x的数放到x的左边，将大于x的数放到x的右边。返回此时基准数的位置。
int partition(int a[], int left, int right) {//将数组a的第left到right个元素进行划分 if(left==right) return left; int i=left,j=right+1; int x=a[left];//基准数 while(1) { while(a[++i]<x && i<right);//左侧 while(a[--j]>x);//右侧 if(i>=j) break; swap(a[i],a[j]); } a[left]=a[j]; a[j]=x; return j; }
find：通过 partition函数获得基准数位置，判断是否为第k小的数，若是则直接输出该数；若不是，则继续在左侧或右侧递归查找第k小的数。
int find(int a[], int left, int right, int k) {//在数组a的第left到right中寻找第k小的数 int mid = partition(a, left, right); if (k - 1 == mid) cout << a[mid]; else if (k - 1 < mid)//判断下一次划分在哪一区间进行 find(a, left, mid - 1, k); else if (k - 1 > mid) find(a, mid + 1, right, k); return 0; }
4、算法时间及空间复杂度
时间复杂度：partition函数需要遍历整个序列，时间复杂度为O(n);find函数运用了二分思想，在最坏的情况下需要处理一半，时间复杂度为T(n/2)，故T(n)=O(n)+T(n/2)=O(n) + O(nlog21)=O(n)。
空间复杂度：在Find函数中使用到了递归调用，需要开辟辅助空间，递归过程空间复杂度为O(logn)，所以总的S(n) = O(logn);
5、心得体会
用快速排序可以提高查找的效率，通过确定基准数最后的位置，在找第k小的数时能够通过基准数的位置来判断第k小的数在哪个范围。通过这个实践加强了对分治法的理解。
原文：https://www.cnblogs.com/bkyhyf/p/13768458.html