第k大元素（经典题目）

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