线性时间选择

问题描述：在一个的数组中（数组中的元素有n个），查找第k小的数。

常规思路：若数组有序，直接输出arr[k-1]即可…

但是…

如果一个数组是无序的话，上面的方法就不太行了，因此需要引入线性时间选择。线性时间选择可以模仿快速排序，基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出来的子数组之一进行递归处理

参数说明：

  • p：数组最左
  • r：数组最右
  • k：要查找的第k小的元素

解题步骤：

  1. 先将数组按五个一组的划分，共有n/5列
  2. 然后利用任意排序方法求出每一列的中位数
  3. 将每一列的中位数按照顺序与原数组的前几位元素互换位置
  4. 再递归求解出中位数的中位数，也就是基准量x
  5. 用得到的基准在整个数组使用快速排序，得到x在数组中的下标i（第j=i+1-p小的数）
  6. 将k和j进行比较，若k≤j，说明要查找的数在j的左边的数组，返回步骤一，继续递归
  7. 反之，则向j的右边的数组递归

不要说了不要说了，先上代码先上代码！

public class Select {
    public static Comparable select(int p,int r,int k,int[] arr){
        if(r-p<75){//如果n＜75，則直接使用任意一个排序方法直接求出第k小的数
           int[] arr1=BubbleSort.bubble(arr);
           return arr1[p+k-1];
        }
        for(int i=0;i<=(r-p-4)/5;i++){//将数组的元素五个为一列，分出i+1列
            int s=p+5*i;//每列的首位元素
            int t=s+4;//每列最后一个元素
            for(int j=0;j<3;j++){//对每列进行冒泡排序，因为我们只要每列（只有五个元素）的中位数，所以只要三趟冒泡排序，将中位数元素"沉底"到中间
                Bubble.bubble(arr,s,t-j);
                Swap.swap(arr,s+2,p+i);//每列的中位数按顺序分别与数组前几位调换位置
            }
        }
        Comparable x=select(p,(r-p-4)/5,(r-p+6)/10,arr);//寻找中位数的中位数x（快速排序的基准）
        int i=Partition.partion(p,r, (Integer) x,arr);//用得到的基准进行快速排序
        int j=i-p+1;//表示第j小的元素
        if (k<=j) return select(p,i,k,arr);//要执行这一步，说明要找的第k小的元素在基准的左边，因此继续向左边递归
        else return select(i+1,r,k-j,arr);//反之亦然
    }
}
赏