python数组中的第K个最大元素（快排与堆排）

题目：数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路：

方法1：最简单的方法就是调用排序的库函数，对数组的元素先进行排序，然后找出第K个最大值（当然这个方法很简单，无法显示编程的水平）

方法2：对于方法1来说，几乎所有编程语言提供的排序的库函数都是基于快速排序而设计的，然而快排的具体实现是如何的呢，接下来，我将手撸快排代码来解决这个问题。

方法3：堆排序方法，建立一个大根堆，删除根节点（并不是完全删除，而是替换到最后面），然后自我调节，第二大的元素就会被交换上来，成为最大的新堆顶，重复上述操作，直到我们所要的第K个最大值成为堆顶节点，然后进行输出根节点的值。

快排原理

1.在数据集中，选择一个元素作为pivot（基准）

2.所有小于“基准”的元素，都移到“基准”的左边；所有大于“基准”的元素，都移到“基准”的右边。这个操作称为partition（分区）

3.对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有的子集只剩下一个元素为止。

选择基准pivot

1.选择第一个元素作为基准

2.随机选择一个元素作为基准

快排的平均时间复杂度是$O(nlogn)$，最坏情况下的时间复杂度是$O(n^2)$，且是一种不稳定的排序方法。

python代码（快排实现）：

class Solution:
    def findKthLargest(self, nums, k):
        # 快排
        self._k = len(nums) - k
        return self.quicksort(nums, 0, len(nums) - 1)

    def quicksort(self, nums, left, right):
        if left == right:
            return nums[left]
        pivot = self.partition(nums, left, right)
        if pivot == self._k:
            return nums[pivot]
        elif pivot < self._k:
            return self.quicksort(nums, pivot + 1, right)
        else:
            return self.quicksort(nums, left, pivot - 1)

    def partition(self, nums, left, right):
        pivot = nums[left]
        i, j = left, right
        while i < j:
            while i < j and nums[j] >= pivot:
                j -= 1
            if i < j:
                nums[i] = nums[j]
                i += 1
            while i < j and nums[i] <= pivot:
                i += 1
            if i < j:
                nums[j] = nums[i]
                j -= 1
        nums[i] = pivot
        return i

堆排序

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。

复杂度：假设二叉堆总共有n个元素，那么向下调整的最坏时间复杂度就等同于二叉堆的高度，也就是$O(nlogn)$

python代码（堆排序实现）

class Solution:
    def findKthLargest(self, nums, k):
        # 堆排
        self._k = len(nums) - k
        return self.heapsort(nums)

    def heapsort(self, nums):
        self.build_heap(nums)
        for i in range(len(nums) - 1, self._k - 1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            # 这里要排除最后一个元素
            self.max_heapify(nums, 0, i)
        return nums[self._k]

    def build_heap(self, nums):
        length = len(nums)
        for i in range(((length - 1) // 2), -1, -1):
            # 从最后一个节点的父节点开始向上调整
            self.max_heapify(nums, i, length)

    def max_heapify(self, nums, i, length):
        left = i * 2 + 1
        right = i * 2 + 2
        if left < length and nums[left] > nums[i]:
            largest = left
        else:
            largest = i
        if right < length and nums[right] > nums[largest]:
            largest = right
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            # 子树也要调整
            self.max_heapify(nums, largest, length)

快排与堆排的时间对比

从结果上看堆排序的运行时间比快排的速度快了10倍，理论上来说，两者的时间复杂度应该差不多，但是为什么出现这样的结果呢，原因应该是黑盒中的测试集数据的设置对堆排序更加友好。

提交提示：

和其他OJ完全不一样，LeetCode的代码不需要你print，甚至不需要你有主函数。它唯一有的就是一个叫做Solution的类，类中有一个函数，返回值和参数都给你写好了，算是一个提示吧。

在这种情况下我们提交代码就要注意以下几点：

1.完全不用担心头文件的问题，他都给你补全好了。

2.你不需要自己补全主函数，只要能够写出可以跑的目标函数就可以了。

3.如果需要引入其他函数，可以直接写在类里面。

本文地址：https://blog.csdn.net/ZXM_SHU/article/details/107105486