线性时间选择

给定线性序集中n个元素和一个整数k，1<=k<=n,要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序列排列时，排在第k个位置的元素即为要找的元素。当k=1时，就是要找的最小元素；当k=n时，就是要找的最大元素；当k=(n+1)/2时就是要找中位数。

在某些特殊情况下，很容易设计出解线性选择问题的线性时间算法。例如，找n个元素的最小元素和最大元素可以在O(n)时间内完成。如何k<=n/logn,通过堆排序算法可以在O(n+klogn)=O(n)时间内找出第k小元素。当k>=n-n/logn时也一样。

一般的选择问题，特别是中位数的选择问题似乎比找最小元素要难。事实上，从渐近阶的意义看，它们是一样的。一般的选择问题也可以在O(n)时间内得到解决。下面看一个模仿快速排序算法实现的线性选择算法。

package sortdemo;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Random;
public class LinearSelect {
    public static void main(String[] args){
        System.out.print("Please input:\n");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        System.out.print("Please input sequence:\n");
        for(int i = 0;i<n;i++){
            arr[i]=scan.nextInt();
        }
        System.out.println(Arrays.toString(arr));
        System.out.print("Please input number you want select:\n");
        int k = scan.nextInt();
        int m = randomSelect(arr,0,arr.length-1,k);
        System.out.println("The number you select is:"+m);
    }
    public static int randomSelect(int[] arr, int left, int right, int k){
        if(left==right){
            return arr[left];
        }
        int i = randomPartion(arr,left,right);
        int j = i-left+1;
        if(k<=j){
            return randomSelect(arr,left,i,k);
        }else{
            return randomSelect(arr,i+1,right,k-j);
        }
        
    }
    public static int randomPartion(int[] arr, int left, int right){
        Random random = new Random();
        int q = left+random.nextInt(right)%(right-left+1);
        swap(arr,left,q);
        return partition(arr,left,right);
    }
    
    public static int partition(int[] arr, int left, int right){
        int temp = arr[left];
        int i = left;
        int j = right;
        while(i<j){
            while(arr[j]>temp&&j>i){
                j--;
            }
            arr[i]=arr[j];
            while(arr[i]<temp&&j>i){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=temp;
        return i;   
    }
    
    public static void swap(int[] arr, int a, int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    
}

在上面的程序中，执行randomSelect后，数组arr[left:right]被划分成两个子数组arr[left:i]和arr[i+1:right],使a[left:i]中每个元素都不大于arr[i+1:right]中每个元素。接着算法计算子数组arr[left:i]中元素个数j。如果k<=j,则arr[left:right]中第k小元素落在子数组a[left:right]中。如果k<j，则要找的第k小元素落在子数组a[i+1:right]中。由于此时已知道子数组a[left:i]中元素均小于要找的第k小元素，因此，要找的a[left:right]中第k小元素是a[i+1:r]中的第k-j小元素。