选择算法

引：300000是不是一个小目标，不知道为了目的还是目的，只想好好努力，功利也好，安慰也罢！

期望为线性时间的选择算法

算法思想：

1. 检查数组是否只有一个数，如是，只好返回该数
2. 采用随机分割将数组氛围a[p..q-1]和a[q+1..r]并返回主元q
3. 检查如果该主元就是我们要找的数，就返回
4. 判断前半部分的个数，如果要找的顺序大于前面的个数，就递归调用后面的数组，否则递归调用前面的数组

代码如下：

import java.util.Random;

public class Randomized_select {
public int randomized_select(int[] a,int p, int r,int i){
//如果分割到只剩一个元素了，那么就是这个了
if(p == r){
return a[p];
}
//随机分割
int q = randompartition(a, p, r);
//确定q是第几小的数
int k = q-p+1;
if(k == i) {
return a[q];
}
else if(k<i){
//递归调用后半部分的数
return randomized_select(a, q+1, r, i-k);
} else {
//递归调用前半部分的数
return randomized_select(a, p, q-1, i);
}		
}
//分割函数
public int partition(int[] a,int p,int r){
int x = a[r];
int i = -1;
int temp = 0;
for (int j = 0; j < a.length-1; j++) {
if(a[j]<x){
i=i+1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = x;
a[r] = temp;
return i+1;
}
//随机分割　
public int randompartition(int[] a,int p,int r){
int temp = 0;
Random random = new Random();
int i = random.nextInt(r);
temp = a[i];
a[i] = a[r];
a[r] = temp;
return partition(a, p, r);
}
public static void main(String[] args) {
int[] a = new int[]{3,2,9,0,7,5,4,8,6,1};
Randomized_select select = new Randomized_select();
int num = select.randomized_select(a, 0, a.length-1, 10);
System.out.println(num);

}
}

算法分析：期望时间复杂度是线性的O(n),但是最坏的时间复杂度是O(n*n)

最坏情况为线性时间的选择算法

算法思想：

1. 将输入数组的n个元素划分为n/5组，每组5个元素，且至多只有一组由剩下的nmod5个元素组成。
2. 寻找每一个组的中位数：首先对每组元素进行插入排序，然后确定每组的中位数。
3. 对第2部的中位数数组利用递归调用前面的random_select()求取中位数x
4. 利用修改的partition(),按中位数x进行划分，得到比x小的数有k个
5. 如果i=k则返回x。如果ik，则在高区递归查找第i-k小的元素

代码如下：

package select;

public class GoodSelect {
//插入排序
public void insertsort(int[] a,int p, int r)
{
for (int i=p+1;i<=r;i++) {
int temp = 0;
//*从后往前插*
for(int j = i;j>p && a[j]<a[j-1];j--){
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}

//对数组A[]分组，每组5个元素，分别进行插入排序,返回中位数数组
public int[] partInsertSort(int[] a,int p,int r)  {
int i = 0;
int[] b;
if((r-p+1)%5==0){
b = new int[(r-p+1)/5];
} else {
b = new int[(r-p+1)/5+1];
}

int Length = r-p+1;
if (Length <= 5)     //元素个数少于5个
{  
insertsort(a,p,r);
b[0]=a[p+(Length-1)/2];
}
else
{
for (i=0;i<Length/5;i++)
{
insertsort(a,p+i*5,p+i*5+4);

b[i]=a[i*5+2];     //B[i] 存储各组中位数
}
if ( Length%5 != 0 )
{
insertsort(a,Length-1-(Length-1)%5,Length-1);
b[i]=a[Length-1-Length%5/2];  //B[i] 存储最后一组中位数
}
}
return b;           //  返回分组的个数

}
//调用random_select算法，选出中位数数组的中位数
public int selectmid(int[] a){
Randomized_select randomized_select = new Randomized_select();
int num = randomized_select.randomized_select(a, 0, a.length-1, (a.length+1)/2);
return num;		
}
//安装精心挑选的中位数来分割数组
public int partition(int[] a,int p,int r,int x){
int j = p-1;
int i = 0;
int temp =0;
int addr = 0;//记录最佳中位数的位置
for(i = p; i<r+1; i++){
if(a[i]<=x){
j+=1;
temp = a[j];
a[j] = a[i];
a[i] = temp;				
}
if(a[i] == x){
addr = i;
}		
}
temp = a[j];
a[j] = a[addr];
a[addr] = temp;
return j;

}
public int goodselect(int[] a,int p,int r,int i){
//如果分割到只剩一个元素了，那么就是这个了
if(p == r){
return a[p];
}
int [] b = partInsertSort(a, p, r);
int x = selectmid(b);
int q = partition(a, p, r, x);
//确定q是第几小的数
int k = q-p+1;
if(k == i) {
return a[q];
}
else if(k<i){
//递归调用后半部分的数
return goodselect(a, q+1, r, i-k);
} else {
//递归调用前半部分的数
return goodselect(a, p, q-1, i);
}
}

public static void main(String[] args) {
int[] a = new int[]{2,1,4,6,5,8,9,7,11,13,12,15,16};
GoodSelect select = new GoodSelect();
int num  = select.goodselect(a, 0, a.length-1, 13);
System.out.println(num);
}
}

算法总结：毕竟是三个人发明的算法，真是好牛逼的，厉害，实现了最坏时间还是线性的。具体分析请参考算法导论原书。

总结

第二个算法真的花了自己好长的时间来调试，还是说明自己的编码能力差劲，要好好努力，慢慢提高，加油！

ps：有一种体会，学算法是为了创造，大多数人只要把优秀的源码包里的算法理解了就好，并加以使用就好！