Python实现快速排序算法及去重的快速排序的简单示例
程序员文章站
2022-05-29 08:57:55
...
快速排序由于排序效率在同为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)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) 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)) #集合自动排序字符串声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
相关文章
相关视频
专题推荐
独孤九贱-php全栈开发教程
全栈 170W+
主讲：Peter-Zhu 轻松幽默、简短易学，非常适合PHP学习入门
玉女心经-web前端开发教程
入门 80W+
主讲：灭绝师太 由浅入深、明快简洁，非常适合前端学习入门
天龙八部-实战开发教程
实战 120W+
主讲：西门大官人 思路清晰、严谨规范，适合有一定web编程基础学习
作者信息
下一篇： 各位前辈，请教一个问题，很烦恼啊
网友评论
文明上网理性发言，请遵守 新闻评论服务协议
我要评论