public class FindTopKth {
    private FindTopKth() {}

    /**
     * @param arr   待查找的数组
     * @param left  待查找数组的左边界
     * @param right 待查找数组的右边界
     * @param k     查找第k小的元素
     * @param <T>   泛型
     * @return 返回第k小的元素
     */
    public static <T extends Comparable<? super T>> T find(T[] arr, int left, int right, int k) {
        int p = partition(arr, left, right, k);
        if (p == k) {
            return arr[p];
        } else if (k < p) {
            return find(arr, left, p - 1, k);
        } else {
            return find(arr, p + 1, right, k);
        }
    }

    private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right, int k) {
        T base = arr[left];
        int j = left;
        for (int i = left+1; i <= right; i++) {
            if (arr[i].compareTo(base) < 0) {
                swap(arr, i, ++j);
            }
        }
        swap(arr, left, j);
        return j;
    }

    private static void swap(Object[] arr, int i, int j) {
        if (i != j) {
            Object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public static <T extends Comparable<? super T>> T find(T[] arr, int k) {
        return find(arr,0,arr.length-1,k-1);
    }

    public static void main(String[] args) {
        Integer[] arr = {3, 1, 9, 7, 5, 11};
        System.out.println(find(arr,1));//第1小的 //1
        System.out.println(find(arr,2));//第2小的 //3
        System.out.println(find(arr,3));//第3小的 //5
        System.out.println(find(arr,4));//第4小的 //7
        System.out.println(find(arr,5));//第5小的 //9
        System.out.println(find(arr,6));//第6小的 //11
    }
}

　　

优质内容筛选与推荐>>
1、[bzoj2115][Wc2011] Xor
2、DataSet
3、公司oracle数据库的一些处理
4、Matrix: android 中的Matrix (android.graphics.Matrix) (转)
5、java数组越界错误