Python解法:实现快排

#考察排序那就手动实现以下快排 顺便熟悉下O(nlogn)  python中的sort()时间复杂度就是O(nlogn)
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here

        def qsort(arr, l, r):
            if l < r:
                p = partion(arr, l, r)#找到一个p 使得小于p的位于arr[l]的左侧，大于arr[l]的在p右侧
                qsort(arr, 0, p - 1)
                qsort(arr, p + 1, r)

        def partion( arr, l, r):
            key = arr[l]
            while l < r:
                while l < r and arr[r] >= key:
                    r -= 1
                arr[l], arr[r] = arr[r], arr[l]
                while l < r and arr[l] <= key:
                    l += 1
                arr[l], arr[r] = arr[r], arr[l]
            return l

        qsort(tinput, 0, len(tinput)-1)
        return tinput[:k] if len(tinput) >= k  else []