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 []
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:22
点赞 评论 收藏
分享
07-20 12:08
已编辑
江南大学 图像识别
机械牛马勇闯秋招:把校园经历里面做过的项目,大作业,课设,毕设啥的,扩写,写成具体的项目经历,自我评价缩写别占篇幅,不然这简历真没东西,初筛都过不了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务