题解 | #最小的K个数#

class Solution:
    def GetLeastNumbers_Solution(self , input, k: int)  :
        # write code here
        # 使用相关的排序方法为，快速排序
        array = input
        array_new = self.quick_sort(array, 0, len(array) - 1)
        return array_new[:k]

    def quick_sort(self, array, start, end):
        if start >= end:
            return array   # 注意递归算法的
        middle_key = array[start]
        low = start
        high = end
        while low < high:
            while low < high and array[high] >= middle_key:
                high-=1
            array[low] = array[high]
            while low < high and array[low] <= middle_key:
                low+=1
            array[high] = array[low]
        # 退出循环
        array[low] = middle_key
        self.quick_sort(array, start, low-1) # 注意这里的start和end的相应的变化
        self.quick_sort(array, low+1, end)
        return array