第k小算法
我們通常會簡單地進(jìn)行一個快速排序后舶担，得到第k個位置上的數(shù)字即可。
我們都知道的是快速排序是個不穩(wěn)定的排序妇汗，它的排序過程簡單的理解主要是兩個概念Partion,pivot(基準(zhǔn)數(shù))
一趟快速排序的過程如下
- 先從序列中選取一個數(shù)作為基準(zhǔn)數(shù)
- 將比這個數(shù)大的數(shù)全部放到它的右邊镇饮，把小于或者等于它的數(shù)全部放到它的左邊
一趟快速排序也叫做Partion，即將序列劃分為兩部分，一部分比基準(zhǔn)數(shù)小吓妆，另一部分比基準(zhǔn)數(shù)大赊时，然后
再進(jìn)行分治過程，因為每一次Partion不一定都能保證劃分得很均勻行拢，所以最壞情況下的時間復(fù)雜度不能
保證總是O(nlogn)的祖秒。
BFPRT算法
在BFPTR算法中，僅僅是改變了快速排序Partion中的pivot值的選取舟奠，在快速排序中竭缝，我們始終選擇第一個元
素或者最后一個元素作為pivot，而在BFPTR算法中沼瘫，每次選擇五分中位數(shù)的中位數(shù)作為pivot抬纸，這樣做的目的
就是使得劃分比較合理，從而避免了最壞情況的發(fā)生耿戚。算法步驟如下
（1）將輸入數(shù)組的n個元素劃分為n/5組湿故，每組5個元素，且至多只有一個組由剩下的n%5個元素組成膜蛔。
（2）尋找n/5個組中每一個組的中位數(shù)坛猪，首先對每組的元素進(jìn)行插入排序，然后從排序過的序列中選出中位數(shù)皂股。
（3）對于（2）中找出的n/5個中位數(shù)墅茉，遞歸進(jìn)行步驟（1）和（2），直到只剩下一個數(shù)即為這n/5個元素的中位數(shù)呜呐，找到中位數(shù)后并找到對應(yīng)的下標(biāo)p就斤。
（4）進(jìn)行Partion劃分過程，Partion劃分中的pivot元素下標(biāo)為p蘑辑。
（5）進(jìn)行高低區(qū)判斷即可战转。
本算法的最壞時間復(fù)雜度為O(n)，值得注意的是通過BFPTR算法將數(shù)組按第K幸郧（大）的元素劃分為兩部分槐秧，而
這高低兩部分不一定是有序的啄踊，通常我們也不需要求出順序，而只需要求出前K大的或者前K小的刁标。
java代碼示意
/**
* Created by ganjun on 2017/5/3.
*/
import java.util.*;
public class BFPRT {
public final int MAXN = 100000;
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個一分組多余的數(shù)字
if(i<=r){
sort(x , i , r);
swap(x , l+index , i+(r-i+1)/2);
index++;
}
if(index == 1) return x[l+index];
else return findMedian(x , l , l+index-1);
}
//尋找x數(shù)組中[l,r]區(qū)間內(nèi)第k小元素
public int findKthMin(int [] x , int l , int r , int k){
int median = findMedian(x , l , r);
// 類似快速排序的方式颠通，確定一個pivot為這個中位數(shù)的值x[l]，然后小的數(shù)放左邊膀懈，大的數(shù)放右邊
// 填坑法顿锰，最開始的數(shù)字x[l]上l位置是空出來的，
// 那么每一輪都從右邊位置j找到一個較小的數(shù)填到i上（最開始i=l)启搂，然后i上空出來了位置硼控，
// 就再從左側(cè)開始找到一個較大的數(shù)填回j上，直到i>=j
int mediemVal = x[l];
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.findMidiem(x , 0 , 6);
int val = sol.findKthMin(x , 0 , x.length-1 , 3);
System.out.println(val);
}
}
c++代碼
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <time.h>
#include <algorithm>
using namespace std;
const int N = 1000005;
int a[N];
int findMedian(int a[] , int l , int r)
{
int i , index;
for(i=l,index=0 ; i+4<=r ; i+=5,index++){
sort(a+l , a+l+5);
swap(a[l+index] , a[i+2]);
}
if(i<=r){
sort(a+i , a+r+1);
swap(a[l+index] , a[i+(r-i+1)/2]);
index++;
}
if(index == 1) return a[l];
else return findMedian(a , l , l+index-1);
}
//以p位置上的數(shù)字作為基準(zhǔn)點劃分胳赌，返回的i是最后基準(zhǔn)點所在的位置
int partion(int a[] , int l , int r , int p)
{
swap(a[p] , a[l]);
int i=l , j=r , pivot= a[i];
while(i<j){
while(i<j && a[j]>=pivot) j--;
if(i<j) a[i] = a[j];
while(i<j && a[i]<=pivot) i++;
if(i<j) a[j] = a[i];
}
a[i] = pivot;
return i;
}
//在a數(shù)組的[l,r]區(qū)間內(nèi)找到第k小的數(shù)字
int findKthMin(int a[] , int l , int r , int k)
{
int median = findMedian(a , l , r);
int p = partion(a , l , r , l);
int len = p-l+1;
if(len == k) return a[p];
else if(len>k) return findKthMin(a,l,p-1,k);
else return findKthMin(a,p+1,r,k-len);
}
int main()
{
int n, k;
while(~scanf("%d", &n)){
scanf("%d", &k);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
int ret = findKthMin(a,0,n-1,k);
//for(int i=0 ; i<n ; i++)
printf("%d\n", ret);
}
return 0;
}
>對于復(fù)雜度的理解有什么問題的可以參考《算法導(dǎo)論》9.3節(jié)牢撼，即112頁