对TopK问题汇总，总体来说也是想把这类问题弄清楚，还有就是排序的问题再复习一遍，以上问题都是以快速排序为核心的，这三种类型必须要牢牢地掌握清楚，透过现象看本质，代码的每一行理解清楚。

1. 获得前K小的数：剑指offer40
2. 获得第K小的数:
3. 获得第K大的数(数组中第k个最大元素)：leetcoad215

获得前K小的数

只有自己写的时候，才会发现有很多的细节没有注意，导致自己的代码运行不下去，所以一些代码的细节是需要推敲和琢磨的。对运行的结果要负责。

# 以下代码经过调试时正确的
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # if k>=len(arr):
        #     return arr
        def quick_sort(arr,left,right):
            # 递归终止条件
            # left=right 证明要处理的数据只有一个
            # left >right 证明右边没有数据
            if left >=right:
                return
            # 定义两个游标分别指向0和末尾的位置，选择基准点为调整范围的第一个值
            start=left
            end = right
            pivot = arr[left]

            # 循环判断，直到遍历全部，left和right两个变量一直在变，直到两个相遇，说明遍历完全部的数据
            while left <right:
                # 从右向左，arr[right]>pivot(从右开始查找大于基准点的值)
                while left < right and arr[right]>=pivot:
                    right-=1
                # 将right索引对应的元素赋值给left
                arr[left]=arr[right]
                # 从左向右的过程中（从左开始查找小于基准点的数）
                while left <right and arr[left]<pivot:
                    left +=1
                # 将left索引对应的值赋值为right
                arr[right] =arr[left]

            # 将基准数放置到对应的位置
            arr[left]=pivot
            
            # 比基准数小的即左边的数 要重复的调用快速排序函数
            if k<left:
                quick_sort(arr,start,left-1)
            # 比基准数大的即右边的数，要重复调用快速排序函数
            if k>left:
                quick_sort(arr,left+1,end)
            # 返回前k小的数
            return arr[:k]
        return quick_sort(arr,0,len(arr)-1)

if __name__=='__main__':
    arr=[3,5,2,1,9,6,-1,0]
    res=Solution().getLeastNumbers(arr,3)
    print(res)

# 后面几行代码稍微有点区别，本质区别不是特别大
# 以下代码经过调试是正确的
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # if k>=len(arr):
        #     return arr
        def quick_sort(arr,left,right):
            # 递归终止条件
            # left=right 证明要处理的数据只有一个
            # left >right 证明右边没有数据
            if left >=right:
                return
            # 定义两个游标分别指向0和末尾的位置，选择基准点为调整范围的第一个值
            start=left
            end = right
            pivot = arr[left]

            # 循环判断，直到遍历全部，left和right两个变量一直在变，直到两个相遇，说明遍历完全部的数据
            while left <right:
                # 从右向左，arr[right]>pivot(从右开始查找大于基准点的值)
                while left < right and arr[right]>=pivot:
                    right-=1
                # 将right索引对应的元素赋值给left
                arr[left]=arr[right]
                # 从左向右的过程中（从左开始查找小于基准点的数）
                while left <right and arr[left]<pivot:
                    left +=1
                # 将left索引对应的值赋值为right
                arr[right] =arr[left]

            # 将基准数放置到对应的位置
            arr[left]=pivot
            quick_sort(arr,start,left-1)
            quick_sort(arr,left+1,end)

        quick_sort(arr,0,len(arr)-1)
        return arr[:k]

if __name__=='__main__':
    arr=[3,5,2,1,9,6,-1,0]
    res=Solution().getLeastNumbers(arr,3)
    print(res)

对函数进行封装

好处：这样的代码层次更加的清晰，方便后续检查与修改，要注意这样的书写方式，值得学习。
用三个函数：Partition()、quick_sort()和topk_split()

from typing import List
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def partition(arr,left,right):
            pivot=arr[left]
            i = left
            j = right
            while i < j:
                while i < j and arr[j] >= pivot:
                    j -= 1
                arr[i] = arr[j]
                while i < j and arr[i] <pivot:
                    i += 1
                arr[j] = arr[i]
            arr[i]=pivot
            return i
        def quick_sort(arr,left,right):
            # 递归的终止条件
            if left <right:
                mid=partition(arr,left,right)
                quick_sort(arr,left,mid-1)
                quick_sort(arr,mid+1,right)

        quick_sort(arr,0,len(arr)-1)
        return arr[:k]

if __name__=='__main__':
    arr=[3,5,2,1,9,6,-1,0]
    res=Solution().getLeastNumbers(arr,3)
    print(res)

from typing import List
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def partition(arr,left,right):
            pivot=arr[left]
            i = left
            j = right
            while i < j:
                while i < j and arr[j] >= pivot:
                    j -= 1
                arr[i] = arr[j]
                while i < j and arr[i] <pivot:
                    i += 1
                arr[j] = arr[i]
            arr[i]=pivot
            return i

        def quick_sort(arr,left,right,k):
            # 递归的终止条件
            if left <right:
                mid=partition(arr,left,right)
                if k<mid:
                    quick_sort(arr,left,mid-1,k)
                if k>mid:
                    quick_sort(arr,mid+1,right,k)
        quick_sort(arr,0,len(arr)-1,k)
        return arr[:k]


if __name__=='__main__':
    arr=[3,5,2,1,9,6,-1,0]
    res=Solution().getLeastNumbers(arr,3)
    print(res)

再进一步进行封装

# 这种做法貌似有点蠢的样子
from typing import List
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def partition(arr,left,right):
            pivot=arr[left]
            i = left
            j = right
            while i < j:
                while i < j and arr[j] >= pivot:
                    j -= 1
                arr[i] = arr[j]
                while i < j and arr[i] <pivot:
                    i += 1
                arr[j] = arr[i]
            arr[i]=pivot
            return i

        def quick_sort(arr,left,right):
            # 递归的终止条件
            if left <right:
                mid=partition(arr,left,right)
                quick_sort(arr,left,mid-1)
                quick_sort(arr,mid+1,right)

        
        def topk_split(nums, k, left, right):
            #寻找到第k个数停止递归，使得nums数组中index左边是前k个小的数，index右边是后面n-k个大的数
            if (left<right):
                index = partition(nums, left, right)
                if index==k:
                    return 
                elif index < k:
                    topk_split(nums, k, index+1, right)
                else:
                    topk_split(nums, k, left, index-1)

        quick_sort(arr,0,len(arr)-1)
        topk_split(arr, k, 0, len(arr)-1)
        return arr[:k]

if __name__=='__main__':
    arr=[3,5,2,1,9,6,-1,0]
    res=Solution().getLeastNumbers(arr,3)
    print(res)

获得第k小的数

做法类似，只是在取k过程中不同

# 调试通过，没有问题
class Solution:
    def getleastKth(self,arr,k):
        # 直接写快速排序的函数（模板）
        def quick_sort(arr,left,right):
            # 判断边界条件
            # left=right说明此时只有一个数据
            # left >right说明右边已经没有数据了
            if left >=right:
                return 

            # 定义两个游标
            start,end=left,right
            # 定义排序范围的起始位置
            pivot=arr[left]

            # 开始进行循环
            while left<right:
                # 当left指针指向的数值小于pivot的值的情况的时候
                while left < right and arr[left]<pivot:
                    left +=1
                # 一旦发现left>=pivot的时候，需要将此时left位置的值赋予给right位置
                arr[right]=arr[left]
                # 当right指针指向的数值大于pivot的时候，需要将right指向向中间靠拢
                while left < right and arr[right]>=pivot:
                    right-=1
                # 一旦发现right<pivot的时候，将此时right位置的值赋予给left对应的位置
                arr[left] = arr[right]
            
            # 循环结束（left >=right）
            # 将pivot的值放在中间的位置
            arr[left]=pivot

            # 对左右两个区间进行相应的排序操作
            quick_sort(arr,start,left-1)
            quick_sort(arr,left+1,end)

        # 由于是求第k小的数
        quick_sort(arr,0,len(arr)-1)
        #print(arr)
        return arr[k]
# 写主函数
if __name__=='__main__':
    arr=[3,5,2,1,9,6]
    res=Solution().getleastKth(arr,3)
    print(res)

采用封装的方式来写

# 代码存在问题，后续补充

获得第k大的数

其实题目的这个条件挺苛刻的，要保证复杂度的要求，这也是我一直在纠结的地方，不过先整理把，这些问题就不管了。
得到答案并不难，但是在不断优化的过程就是挺难的
全局排序：如果是采用python内置的排序，当然时最简单的,当然这种方式打不到训练的目的是一种全局排序的方式，时间复杂度取决于排序的算法
局部排序：只排序TopK个数，O(n*k)，冒泡、直接选择、直接插入都可以，但k的取值趋近n时，时间复杂度又趋近与O(n^2)。

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # 对a进行快速排序
        a.sort()
        return a[-K]

采用快速排序的方式

# 采用这样的一种方式会超时（针对牛客网上）
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        self.quick_sort(a,0,n-1)
        return a[-K]
    
    def quick_sort(self,arr,left,right):
        if left >=right:
            return 
        start=left
        end = right
        pivot = arr[left]
        while left < right:
            while left<right and arr[right]>=pivot:
                right-=1
            arr[left] = arr[right]
            while left <right and arr[left] <pivot:
                left +=1
            arr[right] =arr[left]
        arr[left]=pivot
        self.quick_sort(arr,start,left-1)
        self.quick_sort(arr,left+1,end)
    ```
对这种方法进行相应的改进操作（暂时没有找到比较好的方法，先放着再说把）

采用堆排序（维护小顶堆或大顶堆大方式：复杂度：O(nlog(n))）：没有时间暂时不看了。