leetcoad链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
视频链接：https://www.algomooc.com/1744.html
属于top k类型的题目
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
使用最原始的暴力的方法如下：

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[:k]

采用借助快速排序的思路来解题：
如果在划分后，基准数正好是第k+1小的数字，基准数左边所有的数字就是题目的最下的k个数
判断每次划分后，基准数在数组中的索引是否等于k,如果是直接返回数组的前k个数字

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k >= len(arr): 
            return arr
        #定义快速排序的函数（相当于只排一部分）
        def quick_sort(left,right):
            # 定义两个游标分别指向0和末尾的位置,选择基准点为该调整范围的第一个值
            start = left
            end = right
            pivot = arr[left]

            #循环判断，直到遍历全部
            while left < right:
                # 从右向左 arr[right]>pivot 则right-=1（从右开始查找大于基准点的值）
                while left < right and arr[right] >= pivot:
                    right -= 1
                # 将right索引对应的元素赋值给left（这个位置的值先移动到左边）
                arr[left] = arr[right]
                 # 从左往右  arr[left]<pivot  则left+=1（从左开始查找小于基准点的值）
                while left < right and arr[left] <pivot:
                    left += 1
                 # 将left索引对应的元素赋值给right（这个位置的值先移动到右边）
                arr[right] = arr[left]
            #将基准数放置到对应的位置（写回改成的值）
            arr[left]=pivot
            
            # 以下的部分不同于快速排序（快速排序是将所有的数字都排好了，这里我只排我需要的那部分就行了。）
            if k < left: 
                return quick_sort(start, left - 1) 
            if k > left: 
                return quick_sort(left + 1, end)
            return arr[:k]

        return quick_sort(0, len(arr) - 1)