第k小算法
我们通常会简单地进行一个快速排序后，得到第k个位置上的数字即可。
我们都知道的是快速排序是个不稳定的排序，它的排序过程简单的理解主要是两个概念Partion，pivot(基准数)
一趟快速排序的过程如下：
- 先从序列中选取一个数作为基准数
- 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边
一趟快速排序也叫做Partion，即将序列划分为两部分，一部分比基准数小，另一部分比基准数大，然后再进行分治过程，因为每一次Partion不一定都能保证划分得很均匀，所以最坏情况下的时间复杂度不能保证总是O(nlogn)的。
BFPRT算法
在BFPRT算法中，仅仅是改变了快速排序Partion中的pivot值的选取，在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot，而在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免最坏情况的发生。算法步骤如下：
- 将输入数组的n个元素划分为n/5组，每组5个元素，且至多只有一个组由剩下的n%5个元素组成。
- 寻找n/5个组中每一个组的中位数，首先对每组的元素进行插入排序，然后从排序过的序列中选出中位数。
- 对于2中找出的n/5个中位数，递归进行步骤1和2，直到只剩下一个数即为这n/5个元素的中位数，找到中位数后并找到对应的下标p。
- 进行Partion划分过程，Partion划分中的pivot元素下标为p。
- 进行高低区判断即可
本算法的最坏时间复杂度为O(n)，值得注意的是通过BFPTR算法将数组按第K小（大）的元素划分为两部分，而这高低两部分不一定是有序的，通常我们也不需要求出顺序，而只需要求出前K大的或者前K小的。
public class BFPRT{
public static void swap(int[] x, int i, int j){
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
public static void sort(int[] x, int l, int r){
for(int i=l; i<=r; i++){
for(int j=i+1; j<=r; j++){
if(x[j]<x[i])
swap(x, i, j);
}
}
}
public int findMedian(int[] x, int l, int r){
int i, index;
for(i=l, index=0; i+4<=r; i+=5, index++){
sort(x, i, i+4)
swap(x, l+index, i+2); //将每组的中位数移至数组前端
}
//处理5个一分组多余的数字
if(i<=r){
sort(x, i, r);
swap(x, l+index, i+(r-i+1)/2); //同上
index++;
}
if(index==1)
return x[l];
else
return findMedian(x, l, l+index-1);
}
//寻找x数组中[l,r]区间内第k小元素
public int findKthMin(int[] x, int l, int r, int k){
int mediemVal = findMedian(x, l, r);
int i = l, j = r;
while(i<j){
while(i<j && x[j]>mediemVal)
j--;
if(i<j)
x[i] = x[j];
while(i<j && x[i]<mediemVal)
i++;
if(i<j)
x[j] = x[i];
}
x[i] = mediemVal;
if(i-l+1==k)
return x[i];
else if(i-l+1 > k)
return findKthMin(x, l, i-1, k);
else
return findKthMin(x, i+1, r, k-(i-l+1));
}
public static void main(String[] args){
int[] x = {2, 3, 6, 5, 7, 9, 4};
BFPRT sol = new BFPRT();
int val = sol.findKthMin(x, 0, x.length-1, 3);
System.out.println(val);
}
}
image.png
