题解 | #最小的k个数#

思路：快排，没啥好说的

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        if len(input) == 0:
            return []
        
        self.quickSort(input, 0, len(input)-1)
        return input[:k]
                
    def quickSort(self, a, left, right):
        
        if left >= right:
            return
        
        l, r = left, right
        flag = a[l]
        while l != r:
            while l < r and a[r] >= flag:
                r -= 1
            a[l] = a[r]
            
            while l < r and a[l] <= flag:
                l += 1
            a[r] = a[l]
        a[l] = flag
        
        self.quickSort(a, left, l)
        self.quickSort(a, l+1, right)