方法一：排序
本题使用排序算法解决最直观，对数组 arr 执行排序，再返回前 k 个元素即可。使用任意排序算法皆可，本文采用并介绍 快速排序 ，为下文 方法二 做铺垫。
快速排序原理：
快速排序算法有两个核心点，分别为 “哨兵划分” 和 “递归” 。
    哨兵划分操作： 以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
    如下图所示，为哨兵划分操作流程。通过一轮 哨兵划分 ，可将数组排序问题拆分为 两个较短数组的排序问题 （本文称之为左（右）子数组）。
    

递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。
如下图所示，为示例数组 [2,4,1,0,3,5] 的快速排序流程。观察发现，快速排序和 二分法 的原理类似，都是以 log 时间复杂度实现搜索区间缩小。


复杂度分析：
时间复杂度 O(N log N) ： 库函数、快排等排序算法的平均时间复杂度为 O(NlogN) 。
空间复杂度 O(N) ： 快速排序的递归深度最好（平均）为 O(logN) ，最差情况（即输入数组完全倒序）为O(N)。
代码： 
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def quick_sort(arr, l, r):
            if l>=r: return
            i, j = l, r 
            while i < j:
                while i < j and tinput[j] >= tinput[l]: j-=1
                while i < j and tinput[i] <= tinput[l]: i+=1
                tinput[i], tinput[j] = tinput[j], tinput[i]
            tinput[i], tinput[l] = tinput[l], tinput[i]
            quick_sort(tinput, l, i-1)
            quick_sort(tinput, i+1, r)
        quick_sort(tinput, 0, len(tinput)-1)
        return tinput[:k]
方法二： 基于快速排序的数组划分
题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。
根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。
根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 truetrue 则直接返回此时数组的前 k个数字即可。
时间复杂度 O(N)
空间复杂度 O(logN) 
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def quick_sort(arr, l, r):
            if l>=r: return
            i, j = l, r 
            while i < j:
                while i < j and tinput[j] >= tinput[l]: j-=1
                while i < j and tinput[i] <= tinput[l]: i+=1
                tinput[i], tinput[j] = tinput[j], tinput[i]
            tinput[i], tinput[l] = tinput[l], tinput[i]
            if k < i:quick_sort(tinput, l, i-1)
            if k > i:quick_sort(tinput, i+1, r)
            return tinput[:k]
        return quick_sort(tinput, 0, len(tinput)-1)


参考资料：