Thinking of finding the k-th largest element in O (n) by fast sorting

O(n) In time complexity, find the second... In the unordered array K Big element .

such as ,4, 2, 5, 12, 3 Such a set of data , The first 3 The big element is 4.

We choose the array interval A[0...n-1] Last element of A[n-1] As pivot, An array A[0...n-1] In situ zoning , So the array is divided into three parts ,A[0...p-1]、A[p]、A[p+1...n-1]. If p+1=K, that A[p] It's the element that requires the solution ; If K>p+1, Note No K Big elements appear in A[p+1...n-1] Section , Let's follow the above idea recursively in A[p+1...n-1] Look for... In this interval . Empathy , If K<p+1, Then we are A[0...p-1] Interval search .

Let's see , Why the time complexity of the above solution is O(n)？

First partition lookup , We need to set the size of n To perform partitioning operations , Need to traverse n Elements . Second partition lookup , We just need to set the size of n/2 To perform partitioning operations , Need to traverse n/2 Elements . By analogy , The number of partition traversal elements is respectively 、n/2、n/4、n/8、n/16.…… Until the interval is reduced to 1.

If we add up the number of elements per partition traversal , Namely ：n+n/2+n/4+n/8+...+1. This is the sum of an equal sequence of numbers , The final sum is equal to 2n-1. therefore , The time complexity of the above solution is O(n).

You might say , I have a stupid idea , Take the minimum value in the array every time , Move it to the front of the array , Then continue to find the minimum value in the remaining array , And so on , perform K Time , The data found is no K The big element ？ however , Time complexity is not O(n) 了 , It is O(K * n).

You might say , The coefficient in front of time complexity can be ignored ？O(K * n) No is equal to O(n) Do you ？ This can't be equated so simply . When K Is a small constant , such as 1、2, The best time complexity is really O(n); But when K be equal to n/2 perhaps n when , The worst-case time complexity is O(n2) 了 .