在未知长度的超大数组中线性时间内查找第k大的元素

import java.util.Random;

public class SearchKthElement {
    private int[] array = null; 
    private int elementPos = -1; 
    private int[] twoKBuffer = null;

    public SearchKthElement(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("k can not bigger than the length of array!");
        }

        this.array = arr;
        this.elementPos = k;
        //分配2k缓冲区
        this.twoKBuffer = new int[2*k];

        streamElementFromArray();
    }

    private int  findElementInBuffer(int begin, int end, int k) {  
        if (k > end - begin) {
            System.out.println("begin : " + begin + " end: " + end + " k:" + k);
            throw new IllegalArgumentException("k in not in valid range");
        }

        //如果数组所有元素重复，那么返回其中任何一个元素
        int v = twoKBuffer[begin];
        int count = 0;
        for (int i = begin+1; i <= end; i++) {
            if (twoKBuffer[i] == v) {
                count++;
            }
        }
        if (count == end - begin ) {
            return twoKBuffer[0];
        }

        Random rand = new Random();
        int pos = begin + rand.nextInt(end+1 - begin);
        int P = twoKBuffer[pos];
        //把小于P的元素搬到左边，大于P的元素搬到右边
        int b = begin, e = end;
        int posOfP = -1;
        while (b < e) {
            if (twoKBuffer[b] < P ) {
                b++;
                continue;
            }


            int temp = twoKBuffer[b];
            twoKBuffer[b] = twoKBuffer[e];
            twoKBuffer[e] = temp;
            if (twoKBuffer[e] == P) {
                posOfP = e;
            }
            e--;
        }
        /*
         * b 和 e 交汇时他们指向的元素可能小于P，为了确保e指向的元素大于等于P，如果此时e指向的元素小于P,那么就要把e往后挪一位
         */
        if (twoKBuffer[e] < P) {
            e++;
        }

        /*
         * 把元素P放在左右两部分元素的分界线上，也就是数组形成如下形式:
         * |********|********|
         *    <P   P   >=P
         * 左边部分小于P,中间是元素P,右边是大于等于P的元素 
         */
        //把P的值放到位置e上
        if (posOfP != -1) {
            int temp = twoKBuffer[e];
            twoKBuffer[e] = twoKBuffer[posOfP];
            twoKBuffer[posOfP] = temp;
        }

        /*
         * 把P左右两边的元素分别打印出来，主要出于调试目的
         */
        System.out.println("Pivot is : " + P);
        System.out.println("first half:");
        for(int i = begin; i < e; i++) {
            System.out.print(" " + twoKBuffer[i]);
        }
        System.out.println("\nsecond half: ");
        for (int j = e; j <= end; j++) {
            System.out.print(" " + twoKBuffer[j]);
        }
        System.out.print("\n");


        if (e - begin == k) {
            //如果P前面包括它自己有k个元素，那么P在当前数组是第k大的元素
            return twoKBuffer[e];
        }

        if (e - 1 - begin >= k) {
            //如果P前面有多于k个元素，那么第k大的元素在P的左边部分
            return findElementInBuffer(begin, e - 1, k);
        } else {
            //如果P左边的元素有t个，t < k, 那么第k大的元素在P的右边，它是右边数组第k-t大的元素
            k = k - (e - begin);
            return findElementInBuffer(e, end, k);
        }
    }



    private void streamElementFromArray() {
        int start = 0;
        int n = 0;
        int count = 0;

        try {
            /*
             * 依次从大数组中读入元素，然后放入2k缓冲区，如果缓冲区被填满，那么查找缓冲区元素中第k大的元素
             */
             while (true) {
                 if (start + count == twoKBuffer.length) {
                     findElementInBuffer(0, twoKBuffer.length - 1, elementPos);
                     count = 0;
                     start = elementPos + 1;
                 }

                 twoKBuffer[start + count ] = array[n];
                 count++;
                 n++;
             }
        }catch (IndexOutOfBoundsException e) {
            findElementInBuffer(0, start + count - 1, elementPos);
        }
    }

    public int getKthElement() {
        return twoKBuffer[elementPos];
    }
}

public class Searching {
     public static void main(String[] args) {
        int n = 30;
        //构造一个含指定个元素的数组
        int[] arr = new int[n];
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(100);
        }


        int k = 8;
        SearchKthElement sk = new SearchKthElement(arr, k);
        System.out.println("The " + k + "th element in array from algorithm is :" + sk.getKthElement());

        Arrays.sort(arr);
        System.out.println("The " + k + "th element in array after sorting is : " + arr[k]);
     }
}