Python实现快速排序算法及去重的快速排序的简单示例
作者:j_hao104 时间:2021-06-02 19:58:09
快速排序由于排序效率在同为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)) #集合自动排序字符串
标签:Python,快速排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
从if else到switch case再到抽象
2010-11-05 18:30:00
Oracle数据库按时间进行分组统计数据的方法
2023-07-14 13:52:56
Facebook是如何设计的[译]
2009-09-17 13:10:00
在OracleE数据库的字段上建立索引的方法
2009-02-26 10:34:00
python实现扫雷小游戏
2023-02-15 11:58:58
![](https://img.aspxhome.com/file/2023/9/76699_0s.gif)
用Python实现web端用户登录和注册功能的教程
2021-03-03 07:49:09
![](https://img.aspxhome.com/file/2023/3/68323_0s.jpg)
用ASP和SQL实现基于Web日历源码
2010-04-24 15:52:00
python套接字流重定向实例汇总
2022-04-15 07:53:41
python中文文本切词Kmeans聚类
2023-06-01 18:35:57
python 密码加密与解密的实现
2023-07-31 04:32:38
![](https://img.aspxhome.com/file/2023/3/61433_0s.png)
python贪吃蛇核心功能实现上
2021-12-06 15:49:18
![](https://img.aspxhome.com/file/2023/6/67866_0s.png)
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
2023-08-16 04:46:47
![](https://img.aspxhome.com/file/2023/7/55387_0s.jpg)
Python中获取图片的大小问题
2022-11-08 21:43:23
ADO.NET数据连接池剖析
2023-06-27 17:23:29
![](https://img.aspxhome.com/file/UploadPic/201211/30/20121130203620988s.png)
Oracle学习笔记(四)
2012-01-05 18:57:33
详解pandas.DataFrame中删除包涵特定字符串所在的行
2023-08-23 23:37:45
![](https://img.aspxhome.com/file/2023/6/76966_0s.png)
SQL Server备份和灾难恢复
2010-07-02 12:54:00
![](https://img.aspxhome.com/file/UploadPic/20107/2/01-39s.jpg)
php输出xml必须header的解决方法
2023-09-11 20:00:16
asp常用数据库连接方法和技巧
2010-05-27 12:28:00
如何将数据访问页绑定到断开连接的 ADO 记录集上?
2009-12-03 20:07:00