搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 碎屑笔记 > 排序之快速排序

排序之快速排序

碎屑笔记 2019-11-08

        

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,本过程利用递归已达到整个数据变成有序列表

from typing import Listimport random
def quick_sort(a: List[int]): _quick_sort_between(a, 0, len(a) - 1)
def _quick_sort_between(a: List[int], low: int, high: int): if low < high: # get a random position as the pivot k = random.randint(low, high) a[low], a[k] = a[k], a[low]
m = _partition(a, low, high) # a[m] is in final position _quick_sort_between(a, low, m - 1) _quick_sort_between(a, m + 1, high)
def _partition(a: List[int], low: int, high: int): pivot, j = a[low], low for i in range(low + 1, high + 1): if a[i] <= pivot: j += 1 a[j], a[i] = a[i], a[j] # swap a[low], a[j] = a[j], a[low] return j
if __name__ == "__main__": a4 = [5, -1, 9, 2, -3, 7] quick_sort(a4) print(a4)

(此代码来源网络)以上代码的实现过程中空间复杂度为O(1)

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《排序之快速排序》的版权归原作者「碎屑笔记」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注碎屑笔记微信公众号

碎屑笔记微信公众号:gh_afa9d35e9474

碎屑笔记

手机扫描上方二维码即可关注碎屑笔记微信公众号

碎屑笔记最新文章

精品公众号随机推荐