【算法】快速选择算法 ( 数组中找第 K 大元素 )

class Solution {

    /**
     * 快速选择算法
     * 第 K 大元素
     * @param k
     * @param array
     * @return
     */
    public int kthLargestElement(int k, int[] array) {
        if (array == null){
            return -1;
        }

        return quickSelect(array, 0, array.length - 1, k);
    }

    // 在 array 数组中, 从 start 到 end 中找到第 k 大元素
    private int quickSelect(int[] array, int start, int end, int k) {
        if (start == end) {
            // 说明此时找到了第 K 大元素
            return array[start];
        }

        // 左右两个指针及中间元素值
        int left = start, right = end, pivot = array[(start + end) / 2];
        while (left <= right) {
            while (left <= right && array[left] > pivot) {
                // 默认自增, 如果遇到一个元素大于中心值, 则退出循环, 记录该元素索引 left
                left++;
            }
            while (left <= right && array[right] < pivot) {
                // 默认自增, 如果遇到一个元素小于中心值, 则退出循环, 记录该元素索引 right
                right--;
            }
            // 交换两个元素
            if (left <= right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;
                // 交换完毕后, 左指针自增, 右指针自减, 继续向后执行
                left++;
                right--;
            }
        }

        // 分割完成, 此时索引的排列 start right left end , 其中 right 和 left 之间可能还有元素
        // 这里涉及到了 3 部分 , start 到 right 之间, right 到 left 之间, left 到 end 之间
        // right 到 left 之间只可能有 1 个数
        // 判定 k 在哪个部分

        if (start + k - 1 <= right) {
            // 左侧部分 : 第 k 个数在 start 到 right 之间
            return quickSelect(array, start, right, k);
        }

        if (start + k - 1 >= left) {
            // 右侧部分 : 第 k 个数在 left 到 end 之间
            // 左侧有 left - start 个数, 总共 k 个数, 在右边只需要找第 k - (left - start) 个数
            return quickSelect(array, left, end, k - (left - start));
        }

        // 如果上述两种情况都不是, 则是中间部分, right 到 left 之间的一个数, 可以写成 right + 1 或 left - 1
        return array[right + 1];
    }
}