1、利用快排，归并排序等，时间复杂度O(nlogn)
def quick_sort(self,array, l, r):
if l < r:
q = self.partition(array, l, r)
self.quick_sort(array, l, q - 1)
self.quick_sort(array, q + 1, r)
def partition(self,array, left, right):
if left >= right:
return
key = array[left]
while left < right:
while left < right and array[right] > key:
right -= 1
array[left] = array[right]
while left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[right] = key
return right
def kthLargestElement(self, k, A):
if len(A) < k:
return None
self.quick_sort(A,0,len(A)-1)
return A[len(A)-k]
2、利用快排的‘标兵’
partition(int[] a, int lo, int hi)方法和快速排序一样，选取该分段中的第一个数为标兵(pivot)。所有大于pivot的数放到其左侧，小于pivot的数放到其右侧。最后返回pivot的位置。在经过一次partition方法之后，根据k和pivot的位置，来选择是对左侧部分还是对右侧部分继续进行partition。该方法时间复杂度为O(n)。
例如，现在有数组[3, 2, 1, 5, 6, 4]，k=2。
在经过第1次partition之后，数组变为[4, 6, 5, 3, 1, 2]，pivot位置为第4个（从1开始计数）。我们要找的是第2大的数，小于pivot的位置，所以该数在pivot的左侧。继续对pivot左侧的部分进行partition。
在经过第2次partition之后，数组变为[5, 6, 4, 3, 1, 2]，pivot位置为第3个（从1开始计数）。继续对pivot左侧的部分进行partition。
在经过第3次partition之后，数组变为[6, 5, 4, 3, 1, 2]，pivot位置为第2个（从1开始计数）。这正是我们要查找的数。返回该数。
def partition(self,array, left, right):
if left >= right:
return
key = array[left]
while left < right:
while left < right and array[right] > key:
right -= 1
array[left] = array[right]
while left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[right] = key
return right
def kthLargestElement(self, k, A):
n = len(A)
if n < k or k <= 0 or n <= 0:
return None
left = 0
right = n - 1
while left < right:
qvoit = self.partition(A, left, right)
if qvoit < n - k:
left = qvoit + 1
elif qvoit > n - k:
right = qvoit - 1
else:
return A[qvoit]
return A[left]
其他解法
https://blog.csdn.net/yc461515457/article/details/51177812
