快速选择算法解决数组中的第 k 个最大元素

题目来源：LeetCode 第 215 题

这道题有三个解法,都是力扣官方题解提供的，我首先想到的前两种，但觉得有点投机取巧，因为是直接调用的python内置函数，一句话就能搞定。力扣官方提供第三种解法，利用经典的快速排序算法的一种变形解决。因为基础不牢，我看了很长时间才弄明白,所以打算写下来加深理解。文章主要介绍第三种解法：

排序： 先对数组进行排序，然后直接返回倒数第 k 个元素，python中直接使用语句 sorted(nums)[-k] 求出最后结果。算法的时间复杂度为 O(NlogN)，空间复杂度为O(1)

堆：创建一个大顶堆，将数组的元素加入到堆中，并保证堆的大小小于等于 k，然后堆中就保留了前 k 个最大元素，这样，堆顶元素就是正确答案。python中有内置的该方法直接求出堆的前 k个最大元素，语句heapq.nlargest(k, nums)[-1]，就可得出最后结果。时间复杂度 : O(Nlogk)，空间复杂度 : O(k)，用于存储堆元素

快速选择算法：

快速选择的思路与快速排序一致，选择一个元素作为基准对数组进行分区，使得基准左侧的元素都小于基准的值，右侧的元素都大于基准的值，不同的是，快速选择并不递归访问双边，而是递归到一侧寻找，这使得平均时间复杂度由 O(NlogN) 降低到O(N)。

python 实现快速排序，分而治之+递归

对基准两侧分别进行递归操作。选择基准，并申请额外的两个空间，遍历数组，将小于枢轴的元素加入到 left 数组，大于基准的元素加入到 right 数组。

快速排序代码：

def quick_sort(data):    
    """QuickSort"""  

    # entry and exit  
    if len(data) >= 2:         
        # select an element as the pvoit
        povit = data[len(data)//2]       

        # define the list to the left and right of the pvoit 
        left, right = [], []  

        # remove the povit from the origin list 
        data.remove(povit)        

        for num in data:            
            if num >= povit:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [povit] + quick_sort(right)    
    else:        
        return data

# example：
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))

# output = [1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

python 实现快速选择算法

对基准的一侧进行递归，寻找第 k 个最大的元素。代码中 partition() 函数作用是对数组进行分区，通过以下三步实现：

将基准移到最右侧；
将小于基准的数移到 pivot_fix 的左侧；
将基准移回 pivot_fix 的位置。

最后该函数返回分区后基准的位置。将位置返回到select()函数中之后，判断该位置是否为 k_smallest(即 len(nums) - k),若是，则返回，若大于 k_smallest，则遍历基准的左侧部分数组，重复之前操作，反之，则遍历基准右侧部分数组，重复之前操作。

力扣第 215 题解题代码：

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def partition(left, right, pivot_index):

            # the value of pivot
            pivot = nums[pivot_index]

            # move the pivot to the right of nums
            nums[right],nums[pivot_index] = nums[pivot_index],nums[right]

            pivot_fix = left
            # move the smaller than the value of pivot to the left
            for i in range(left,right):
                if nums[i] < pivot:
                    nums[pivot_fix],nums[i] = nums[i],nums[pivot_fix]
                    pivot_fix += 1

            # move the pivot to the original index
            nums[right],nums[pivot_fix] = nums[pivot_fix],nums[right]

            return pivot_fix

        def select(left, right, k_smallest):
            """
            Returns the k-th smallest element of list within left..right
            """
            if left == right:
                return nums[left]

            # select pviot
            pivot_index = nums[left]

            pivot_index = partition(left,right,pivot_index)

            if pivot_index == k_smallest:
                return nums[pivot_index]

            # do left
            elif pivot_index > k_smallest:
                return select(left,pivot_index - 1,k_smallest)

            # do right
            else:
                return select(pivot_index + 1,right,k_smallest)

        # kth largest is (n - k)th smallest
        return select(0, len(nums) - 1, len(nums) - k)


res = Solution()
output = res.findKthLargest([4,3,5,1,6,2], k = 4)
print(output)