題意

求一個未排序數組的第k大。

思路

算法1

O(nlogn)$O(nlogn)$的復雜度。

先排序，然后直接返回第k大即可。

算法2

期望時間為O(n)$O(n)$，最壞時間為O(n2)$O(n^2)$的算法。

其基本思想就是基于快排。

首先，我們選擇一個觀察哨x，將≥x$/geq x$的元素放在x左邊，小于x的元素放在x的右邊。

然后，如果x此時的位置pos+1==k$pos + 1 == k$，說明x即為我們要求的元素。

否則， 如果pos+1>k$pos + 1 > k$，說明x過小，那么要求的元素應該在[l, pos - 1]之間。

否則， 要求的元素在[pos + 1, r]之間。

在算導第三版的P120-P122有對該算法時間復雜度的證明。

代碼