复习归并排序

class Solution(object):
    def getLeastNumbers_Solution(self, input, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """
        nums = input
        n = len(nums)
        self.merge_sort(nums,0,n-1)
        return nums[:k]

    def merge_sort(self,nums,l, r):
        if l>=r:
            return 

        res = []
        mid = (l+r)>>1

        self.merge_sort(nums,l,mid)
        self.merge_sort(nums,mid+1,r)

        i=l
        j=mid+1
        while i<=mid and j<=r:
            if nums[i]<=nums[j]:
                res.append(nums[i])
                i+=1
            else:
                res.append(nums[j])
                j+=1

        while i<=mid:
            res.append(nums[i])
            i+=1

        while j<=r:
            res.append(nums[j])
            j+=1

        for x in range(l,r+1):
            nums[x]=res[x-l]

堆排序

class Solution(object):
    def getLeastNumbers_Solution(self, input, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """
        nums = input
        n=len(nums)
        heap = [0 for x in range(0,k+1)]
        size = k

        for i in range(1,k+1):
            heap[i]=nums[i-1]

        for i in range(k//2,0,-1):
            self.down(heap,i,size)

        for i in range(k,n):
            x = nums[i]
            if x < heap[1]:
                heap[1]=x
                self.down(heap,1,size)

        res = []

        for i in range(0,k):
            res.insert(0,heap[1])
            heap[1]=heap[size]
            size-=1
            self.down(heap,1,size)

        return res

    def down(self,heap,i,size):
        t=i
        if i*2<=size and heap[2*i]>heap[t]:
            t=2*i

        if i*2+1<=size and heap[2*i+1]>heap[t]:
            t=2*i+1

        if t!=i:
            temp = heap[i]
            heap[i]=heap[t]
            heap[t]=temp
            self.down(heap,t,size)