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

分而治之的思想体现_快速排序

wawees 2019-11-08

快速排序

 1#快速查询
2
3def quicksort(array):
4    if len(array) < 2:  #如果输入数组为空或者只有一个元素,则直接返回该数组
5        return array
6    else:
7        pivot =  array[0]
8        print("array:",array)
9        print("pivot=",pivot)
10        less = [i for i in array[1:] if i <= pivot]
11        print("less:",less)
12        greater = [i for i in array[1:] if i > pivot]
13        print("graeter:",greater,"\n")
14        return quicksort(less) + [pivot] + quicksort(greater)
15
16print(quicksort([3,1,7,4,0,6,9]))

直接结果:

 1array: [3174069]
2pivot= 3
3less: [10]
4graeter: [7469
5
6array: [10]
7pivot= 1
8less: [0]
9graeter: [] 
10
11array: [7469]
12pivot= 7
13less: [46]
14graeter: [9
15
16array: [46]
17pivot= 4
18less: []
19graeter: [6
20
21[0134679]

执行流程

1、优先从layer1开始进行分裂,以3为初始条件进行大小比较,分为less和greater。然后再针对分裂后的每一个数组进行下一次分裂,按照第一次方法。整个数组已树形结构展开后,直到每个分支只有一个元素或者无元素作为递归的终点。


2、将分裂的结果重新组合,从layer1的结果作为处理分支,优先处理less部分,从最底层往上进行汇总按照less+pivot+greater的方式组合;再加上layer1指定的pivot;最后处理greater部分,从最底层往上进行汇总 less + pivot +greater。


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

文章来源: 阅读原文

相关阅读

关注wawees微信公众号

wawees微信公众号:wawees

wawees

手机扫描上方二维码即可关注wawees微信公众号

wawees最新文章

精品公众号随机推荐