Order Statistics

T215 数组中的第K个最大元素，常见面试题，也是算法导论9.2/9.3一节中Order Statistics一节的内容，在线性时间内查找数组中第K个最大的元素，将学习过程整理到本文中。

Partition

partition是快排的核心思想，即选定一个pivot，把比pivot小的元素甩到pivot左边，比它大的元素甩到其右边，最终返回的是pivot所在的index。

具体实现时，参照书上的思路，选定最后数组里最后一个值为pivot。用j遍历数组，用i、j两个指针标记，循环不变式为：arr[begin,i]≤pivot，arr[i+1,j-1]>pivot。

遇到比pivot小的，i右移，比pivot小的数增多。交换j和i。

遇到比pivot大的，j右移。

int partition(int[] arr, left, right){
    int pivot = arr[right];
    int i = left - 1;//arr[left..i]表示比pivot小的数
    for(int j = left; j < right; j++)
        if (arr[j] < pivot)
        {
            i++;
            swap(arr,i,j);
        }
    swap(arr,i+1,j)
    return i+1;
}

顺序统计量

寻找第K大的，即寻找index为length-K的数。

核心思想就是利用partition，只处理划分后的半边。直到partition选择的pivot的index即为第K大的数。

int Solution(int[] arr, int k){
    int target = arr.length - k;
    int left = 0;
    int right = arr.length-1;
    while (true){
        int index = partition(arr,left,right);
           if (index == target)
                return arr[index];
        else if (index < target)
                left = index + 1;
        else right = index - 1;
    }

}

void swap(int[] arr,int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}