剑指最小的k个数

通过快速排序，然后取最小的k个数。

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

        def quick_sort(left,right):
            i=left
            j=right
            if i>j:
                return 
            while i<j:
                while tinput[j]>tinput[left] and i<j:
                    j-=1
                while tinput[i]<=tinput[left] and i<j:
                    i+=1
                tinput[i],tinput[j]=tinput[j],tinput[i]

            tinput[left],tinput[i]=tinput[i],tinput[left]

            quick_sort(left, i-1)
            quick_sort(i+1, right)
        if k<0 or k>len(tinput):
            return []
        quick_sort(0,len(tinput)-1)  
        return tinput[:k]

归并排序，先分开，分到只剩一个元素，然后再将元素放在一起。
其中两个数组中元素放在一起时，可以通过result+=left[i:] result+=right[j:] 加入剩下的元素。

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def merge(linput,rinput):
            result=[]
            l=len(linput)
            r=len(rinput)
            if l==0 or r==0:
                return 
            i=0
            j=0
            while i<l and j<r:
                if linput[i]<rinput[j]:
                    result.append(linput[i])
                    i+=1
                else:
                    result.append(rinput[j])
                    j+=1
#             if i<l:
#                 while i<l:
#                     result.append(linput[i])
#                     i+=1
#             if j<r:
#                 while j<r:
#                     result.append(rinput[j])
#                     j+=1
            result+=linput[i:]
            result+=rinput[j:]
            return result


        def merge_sort(left,right):
            if left==right:
                return [tinput[left]]

            mid=(right-left)//2+left
            left_sort=merge_sort(left,mid)
            right_sort=merge_sort(mid+1,right)
            return merge(left_sort,right_sort)
        if k<0 or k>len(tinput) or len(tinput)==0:
            return []
        tresult=merge_sort(0,len(tinput)-1)
        return tresult[:k]

堆排序 先从最后一个非叶子节点一直到0结点，(n-1)//2-0 调整（初始化）堆。然后将首尾位置结点交换，继续调整堆。调整是通过判断左右结点哪一个更大，是否大于父节点，来判断进行交换。有几种方式，一种最开始结点一步到位交换到最终位置，一种是通过一直交换位置，到达最合适的位置。

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def adjust_head(tinput,startpos,endpos):
            #temp=tinput[startpos]

            childpos=2*startpos+1
            while childpos<=endpos:
                rightpos=childpos+1
                if rightpos<=endpos and tinput[rightpos]>=tinput[childpos]:
                    childpos=rightpos
                if tinput[childpos]>tinput[startpos]: # 如果大于最开始遍历的结点值，那么就交换，这样最开始的结点可以放在最适合他的位置上


                    tinput[startpos],tinput[childpos]=tinput[childpos],tinput[startpos]#直接交换 最开始结点值不一定落在最终位置上

                startpos=childpos
                childpos=2*startpos+1
#                 else:
#                     break
            #tinput[startpos]=temp



        n=len(tinput)
        lastparent=(n)//2
        for i in range(1,lastparent+1):
            adjust_head(tinput,lastparent-i,n-1)
        for i in range(n-1,-1,-1):
            tinput[0],tinput[i]=tinput[i],tinput[0]
            adjust_head(tinput,0,i-1)
        if k<0 or k>len(tinput) or len(tinput)==0:
            return []
        return tinput[:k]

也可以两个循环 都从下至上，从最后一个非叶子结点到根节点。

        n=len(tinput)
        lastparent=(n)//2
        for i in range(1,lastparent+1):
            adjust_head(tinput,lastparent-i,n-1)
        for i in range(n):
            lastparent=(n-i-1)//2
            tinput[0],tinput[n-i-1]=tinput[n-i-1],tinput[0]
            for t in range(1,lastparent+1):
                adjust_head(tinput,lastparent-t,n-i-2)
        if k<0 or k>len(tinput) or len(tinput)==0:
            return []
        return tinput[:k]