# 题目描述

在一个由 $n$ 个元素组成的集合中，第 $i$ 个顺序统计量是指该集合中第 $i$ 小的元素，下面介绍一种期望为线性时间的顺序统计量算法。

先给出顺序统计量函数 SELECT(A,p,r,i) 的伪代码，它返回数组 $A[p...r]$ 中第 $i$ 小的元素：

SELECT( A, p, r, i)

1	if p == r

2		return A[p]

3	q = PARTITION( A, p, r)

4	k = q - p + 1

5	if i == k

6		return A[q]

7	else if i < k

8		return SELECT( A, p, q-1, i)

9	else 

10		return SELECT( A, q+1, r, i-k)

函数的第一行检查递归的基本情况，即 $A[p...r]$ 中只包含一个元素，在这种情况下 $i$ 必然等于 $1$，直接返回 $A[p]$；第三行的 PARTITION(A,p,r) 自动将数组分为 $A[p...q−1]$ 和 $A[q+1...r]$ 两部分，并返回分界元素的下标 $q$，其中 $A[p...q−1]$ 中的每个元素都小于或等于 $A[q]$，$A[q+1...r]$ 中的每个元素都大于 $A[q]$；第四行计算子数组 $A[p...q]$ 中的元素个数 $k$，如果 $k$ 等于 $i$，那就说明 $A[q]$ 就是 $A[p...r]$ 中第 $i$ 小的元素，直接返回；第七行中，如果 $i$ 小于 $k$，说明第 $i$ 小的元素在前一半区间中，数组 $A[p...r]$ 中第 $i$ 小的元素就是数组 $A[p...q−1]$ 中第 $i$ 小的元素；第九行中，否则，说明第 $i$ 小的元素在后一半区间中，数组 $A[p...r]$ 中第 $i$ 小的元素就是数组 $A[q+1...r]$ 中第 $i−k$ 小的元素（因为保证了前一半数组中的元素和 $A[q]$ 都比后一半数组中的元素小）。

下面再给出 PARTITION(A,p,r) 一种实现的伪代码，其作用是用元素 $A[r]$ 将数组 $A[p...r]$ 分为左右两半，左面一半中的元素都小于 $A[r]$，右面一半中的元素都大于 $A[r]$，最后再把元素 $A[r]$ 放在它们中间，并返回 $A[r]$ 在分割完的数组中的位置，以达到划分的效果：

PARTITION( A, p, r)

1	x = A[r]

2	i = p - 1

3	for j = p to r - 1

4		if A[j] <= x

5			i = i + 1

6			exchange A[i] with A[j]

7	exchange A[i+1] with A[r]

8	return i + 1

下面请你根据上面的伪代码实现顺序统计量函数，注意上面的实现只是期望时间为线性，对于一些特殊的输入最坏情况下算法的复杂度为平方级，在此我们保证对于我们的测试数据，对照上面的伪代码实现就能通过。

# 输入格式

第一行两个正整数 $n, k$，分别数组中有 $n$ 个数，找到第 $k$ 小的元素，保证 $1 \le n \le 4000000$，$1 \le k \le n$。

第二行 $n$ 个整数，第 $i$ 个正整数即为数组的第 $i$ 个元素 $A_i$，保证 $−10^7 \le A_i \le 10^7$，且所有元素互不重复。

# 输出格式

一个整数，表示原数组中第 $k$ 小的元素。

# 输入样例

5 3

-5 -7 8 -6 4

# 输出样例

-5

# 题解：快速排序 + 模拟

这个题直接给出了这个算法的伪代码，所以写起来非常好写。其实这个算法就是 C++ 中的 nth_element() 函数的原型，该函数就是在线性的时间复杂度内求出数组的第 $k$ 大 / 小数。关于时间复杂度的证明：

对于随机数据，期望每经过一次 PARTITION 操作后都能将数组对半分，每次 PARTITION 操作的复杂度为区间长度，因此 $n + \dfrac n 2 + \dfrac n 4 + \cdots \to 2n$，因此时间复杂度期望是线性的。

参考代码：

#include <stdio.h>

int n, k, a[4000010];

void Swap(int *a, int *b)

{

    int t = *a;

    *a = *b;

    *b = t;

    return;

}

int Partition(int a[], int p, int r)

{

    int x = a[r], i = p - 1;

    for (int j = p; j < r; ++ j)

        if (a[j] <= x)

            Swap(&a[ ++ i], &a[j]);

    Swap(&a[i + 1], &a[r]);

    return i + 1;

}

int Select(int a[], int p, int r, int i)

{

    if (p == r)

        return a[p];

    int q = Partition(a, p, r);

    int k = q - p + 1;

    if (i == k)

        return a[q];

    else if (i < k)

        return Select(a, p, q - 1, i);

    else

        return Select(a, q + 1, r, i - k);

}

int main()

{

    // freopen("H.in", "r", stdin);

    // freopen("H.out", "w", stdout);

    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; ++ i)

        scanf("%d", &a[i]);

    printf("%d\n", Select(a, 1, n, k));

    return 0;

}