题解 | #最小的K个数#

method 1: sort（）nlogn 但是结果并不需要排好序，所以做了很多无用功

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        tinput.sort()
        return tinput[:k]

method 2: partition思想 n 但是多次访问数据，如果n很大，尽量想避免使用过多的数据；快排partition需要处理两边 所以是nlogn

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if not tinput:
            return []

        return self.partition(0, len(tinput)-1,tinput,k)


    def partition(self, start, end, tinput, k):
        if start > end:
            return tinput[:k]

        left, right = start, end
        pivot = tinput[(start + end)//2]

        while left <= right:
            while left <= right and tinput[left] < pivot:
                left += 1
            while left <= right and tinput[right] > pivot:
                right -= 1

            if left <= right:
                tinput[left], tinput[right] = tinput[right], tinput[left]
                left += 1
                right -= 1

        if k <= right:
            self.partition(start, right, tinput, k)
        if k >= left:
            self.partition(left, end, tinput, k)

        return tinput[:k]

method 3: 使用优先序列，每次和堆顶比较，n