黑松山资源网 Design By www.paidiu.com
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
现在通过一个实例来说明快排。
比如有一个数组:
6 2 4 5 3
第一步:选取一个基准数,不要被这个名词吓到了,你可以把它看作是一个比较大小的数,因为排序就是比较大小,
比如我选取最后一个数3为基准数,依次把数组的数和3比较,比3小的放左边,比3大的放右边,这样有如下结果:
2 3 6 4 5
第二步:判断区间个数,经过第一步后左边区间只有一个数了,没有数字再和它比较了,因此不需要重复操作,右边区间还有:
6 4 5
重复第一步,选取5作为基准数,得到比较结果:
4 5 6
这样左右两边区间都只有一个数了,这就标志着排序完成,最后把所有区间合并就得到排序结果:
2 3 4 5 6
def quick_sort(array): less = []; greater = [] if len(array) <= 1: return array pivot = array.pop() for x in array: if x <= pivot: less.append(x) else: greater.append(x) return quick_sort(less) + [pivot] + quick_sort(greater) list = [2,4,2,6,7,8,1]
print quick_sort(list)
[1, 2, 2, 4, 6, 7, 8]
相比C、C#、JAVA之类的是不是简单多了^.^
TIP:去重的快速排序
如下, 只需要把集合修改为单值元素,这里我们使用Python3来演示:
# -*- coding: utf-8 -*- import random L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] def qsort(L): if len(L)<2: return L pivot_element = random.choice(L) small = [i for i in L if i< pivot_element] #medium = [i for i in L if i==pivot_element] large = [i for i in L if i> pivot_element] return qsort(small) + [pivot_element] + qsort(large) print(qsort(L))
输出:
[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]
也可以直接使用, 集合(set)进行排序和去重.
mylist = list(set(L)) #集合自动排序字符串
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- s14全球总决赛瑞士轮赛制是什么 全球总决赛瑞士轮赛制详情
- 《COD21》全新剧情宣传片:10月25日XGP见!
- 美国拳王家门口身中7枪遇害 年仅31岁凶手仍未被逮捕
- 《寂静岭2》重制版光追对比:氛围更加恐怖
- 林慧萍.1982-往昔(飞跃复刻版)【歌林】【WAV+CUE】
- 陈楚生.2007-原来我一直都不孤单(EP)【天娱传媒】【WAV+CUE】
- 罗嘉良.1986-秦始皇(2014环球复黑王·百代篇)【EMI百代】【WAV+CUE】
- 2024周年庆赠送物品介绍,周年庆送什么
- 【原神】V5.0攻略 |「明黄曜石断片」全收集
- 【原神】V5.0攻略 | 隐藏成就「烦请高抬贵脚」达成
- 证声音乐图书馆《蔚蓝海岸·爵士度假日》[FLAC/分轨][155.47MB]
- 腾讯音乐人《浪漫火焰(新势力计划合辑 Vol.11)》[320K/MP3][56.91MB]
- 腾讯音乐人《浪漫火焰(新势力计划合辑 Vol.11)[FLAC/分轨][147.45MB]
- 2024年,哪里还可以玩有趣的魔兽RPG?
- 类银河恶魔城动作游戏《灵魂熔解》已正式登陆Steam