40. 最小的k个数

https://blog.nowcoder.net/n/abe0690b7ed743199af1f708da1fdb37
复习的时候要再好好想一下排序算法
利用快排

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput):
            return ''
        first = 0
        last = len(tinput) - 1
        index = self.partition(tinput, first, last)
        while index != k-1:
            if index > k-1:
                index = self.partition(tinput, first, index-1)
            if index < k-1:
                index = self.partition(tinput, index+1, last)
        return sorted(tinput[:k])

    def partition(self,alist,first,last):
        pivotvalue = alist[first]
        leftmark = first + 1
        rightmark = last
        done = False
        while not done:
            while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
                leftmark += 1
            while alist[rightmark] >= pivotvalue and leftmark <= rightmark:
                rightmark -= 1
            if rightmark < leftmark:
                done = True
            else:
                alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]
        alist[first],alist[rightmark] = alist[rightmark],alist[first]
        return rightmark