查找第K大的元素

/**
 * 查找一个无序数组中 第K大的元素
 * 这里我们可以使用快排 分区 分治的思想去解决
 * <p>
 * 先按分区点 分区，然后判断分区点的值 是大于还是小于第K大元素，然后再递归接着处理，直接找到值
 */
public class findK {
    public static void main(String[] args) {

        int[] array = {6, 3, 4, 8, 1, 6};

        System.out.println(findK(array, 2, 0, array.length - 1));
    }

    private static int findK(int[] array, int k, int start, int end) {
        if (k > end + 1 || k < 0) return -1;

        if (start >= end) return array[start];

        int index = findPortionIndex(array, start, end);

        if (index + 1 == k) return array[index];
        else if (index + 1 > k) return findK(array, k, start, index - 1);
        else return findK(array, k, index + 1, end);
    }

    /**
     * 获取分区点的下标值, 同时对数据源进行分区
     */
    private static int findPortionIndex(int[] array, int start, int end) {

        int index = start;

        int point = array[end];

        for (int i = start; i <= end; i++) {

            //这里我们只把大于分区点的元素 移动到前面
            if (array[i] > point) {
                int tmpValue = array[i];
                array[i] = array[index];
                array[index] = tmpValue;
                index++;
            }
        }

       //因为前面的比较 是大于分区点的， 所以在最后的时候，需要把分区点放到 所有小于它的值的前面，
       //这里我们只需要把 把分区点和第一个比它小的值 交换一下就可以了，避免了数据的迁移，这里我个人觉得是很精髓的，大大减小了数据迁移的工作量.  
        array[end] = array[index];
        array[index] = point;

        return index;
    }
}