顺序统计的问题是：

给定一组元素，找到其中第k大（小）的元素

仅从功能实现上考虑，完全可以先对数组排序，然后直接取nums[k-1]作为结果输出。但这个方法是需要先对数组排序的，所以效率为$\Theta(nlogn)$，我们的目标是找到一种$\Theta(n)$的方法

基于随机数的分治法

为了尽量压缩时间，可以考虑能不能在排序进行时就顺便找到所需元素，为此，可以使用快速排序算法中的分治思想

在快速排序算法中，每选定一个基准数pivot，就需要将所有小于pivot的元素移动至其左侧、所有大于pivot的元素移动至其右侧，当全部移动完成时，左右指针会正好相遇在pivot元素上

不难想到，当获得了pivot的索引值index，就可以直接检查index是否正好等于k-1（假设k指第k小的元素值），如果相等，则说明这个pivot就是要找的第k小的元素；如果不等，则进一步检查index与k-1之间的大小关系并确定新pivot：

  • 如果index > k-1，说明要寻找的元素相较于pivot来说更小，那么去小于pivot的区域再找
  • 如果index < k-1，说明要寻找的元素相较于pivot来说更大，那么去大于pivot的区域再找

以上过程完全可以用递归来实现（事实上这也是快速排序所进行的过程），而在区域中选取pivot实际上是随机取得的。另外，当传入的左右限制left == right时，说明此区域仅有一个元素，需要寻找的只能是该元素，直接返回nums[left]即可

代码实现（Java）

类的总体结构应为：

import java.util.Random;
class Find {
    private int[] nums;
    private int k;
    public Find(int[] nums) {...}
    public int getKElement(int k) {...}
    private int randomSelect(int left, int right) {...}   // 递归部分，选取随机数、划分后判断
    private int partition(int random, int p, int q) {...}   // 划分部分
    private void swap(int i, int j) {...}   // 用于交换数组元素的工具方法
}

先编写划分部分的方法，输入数组、随机索引值、左右限制，输出划分后pivot的索引值：

public int partition(int random, int p, int q) {
    while (p != q) {
        int pivot = nums[random];
        while (pivot > nums[p]) p++;
        swap(nums, p, random);
        random = p;
        while (pivot < nums[q]) q--;
        swap(nums, q, random);
        random = q;
    }
    return random;
}

编写递归部分：

private int randomSelect(int left, int right) {
    if (left == right) return nums[left];   // 仅余一元素，必定是目标
    Random rand = new Random();
    int rInd = rand.nextInt(right - left + 1) + left;
    int index = partition(nums, rInd, left, right);
    if (index == k-1) return nums[index];   // 划分后，判断该随机元素是否命中
    else if (index > k-1) return randomSelect(left, index-1, k);   // index > k-1，去index左侧划分
    else return randomSelect(index+1, right, k);   // index < k-1，去index右侧划分
}

核心部分已经完成，只需要调用即可：

public int getKElement(int k) {
    return randomSelect(0, nums.length-1);
}

通过测试输出，可以直观地看到这个算法的执行过程，通俗来讲就是一边进行快速排序，一边找到目标元素：