此算法在数组中没有重复元素的情况下起作用。

This algorithm works assuming there's no repeated elements in the array.

找到中值元素，然后在该元素上旋转数组。然后继续对数组的较小部分应用此过程，直到找到单个元素为止。

Find the median element, and pivot the array on that element. Then keep applying this procedure on the smaller half of the array until you're down to a single element.

在每个步骤A处调用数组的较大一半（ m），A（m-1），....，A（0）大约m。 A（0）的大小始终为1，并且每个连续的数组是前一个数组的两倍或加一。也就是说，len（A（0））= 1，len（A（n））= len（A（n-1））或len（A（n-1））+ 1。注意，2 ^ n< = len（A（n））< 2 ^（n + 1）。

Call the larger-half of the arrays at each step A(m), A(m-1), ...., A(0) for some m. A(0) is always of size 1, and each consecutive array is either double the size of the previous array or that plus one. That is, len(A(0)) = 1, len(A(n)) = len(A(n-1)) or len(A(n-1))+1. Note that 2^n <= len(A(n)) < 2^(n+1).

查找长度为n的数组的中值需要O（n）时间（使用众所周知的线性时间中值发现算法） ，并且进行枢转也需要O（n）时间。您正在递归应用此函数（在较小的一侧），这总体上需要n + n / 2 + n / 4 + ... = O（n）时间。

Finding a median of an array of length n takes O(n) time (using a well-known linear time median finding algorithm), and pivoting also takes O(n) time. You're applying this recursively (on the smaller side), which overall takes n + n/2 + n/4 + ... = O(n) time.

将S（n）定义为A（0），A（1），...，A（ n-1）。 （S（0）= 0）。

Define S(n) to be the sum of lengths of A(0), A(1), ..., A(n-1). (S(0) = 0).

找到n，使得S（n）< = k，并且S（n + 1）> k。您可以在O（log k）时间完成此操作。

Find n such that S(n) <= k, and S(n+1) > k. You can do this in O(log k) time.

然后，在A（n）中找到k-S（n）最大元素。使用快速选择算法（的确定性变体），可以在O（len（A（n）））时间内完成此操作。由于len（A（n））是Theta（k），因此可以在O（log k）+ O（k）= O（k）的时间内找到该元素。

Then, find the k-S(n) largest element in A(n). This can be done in O(len(A(n))) time using the (deterministic variant of the) quickselect algorithm. Since len(A(n)) is Theta(k), this element has been found in O(log k) + O(k) = O(k) time.

首先考虑n为2的幂乘以1的情况会更容易。然后，子数组A（i）的大小加倍。例如，当n为16且输入按某种顺序为数字0到15时，子数组可能如下所示：

It's easier to first consider the case where n is a power of 2 minus 1. Then the subarrays A(i) double in size. For example when n is 16, and the input is the numbers 0 to 15 in some order, the subarrays might look like this:

A(0) = [0]
A(1) = [2, 1]
A(2) = [6, 3, 4, 5]
A(3) = [15, 8, 11, 10, 7, 12, 13, 9, 14]

查找如果找到第7个最大元素，则它必须位于A（2）中，并且在A（0）和A（1）中有3个元素组合，因此我们需要在A（2）中找到7-3 =第4个最大元素。我们使用quickselect来做到这一点。

To find the 7th largest element, we find it must lie in A(2) and there's 3 elements combined in A(0) and A(1), so we need to find the 7-3 = 4th largest element in A(2). This we do using quickselect.