Python实现快速排序算法及去重的快速排序的简单示例-Python教程-PHP中文网

首页

后端开发

Python教程

Python实现快速排序算法及去重的快速排序的简单示例

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jul 06, 2016 pm 01:29 PM

python 快速排序排序算法

快速排序由于排序效率在同为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)) #集合自动排序字符串

登录后复制

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

热工具

热门话题

gmail邮箱登陆入口在哪里

7454

CakePHP 教程

1375

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

显示更多

Related knowledge

PS一直显示正在载入是什么原因？ Apr 06, 2025 pm 06:39 PM

PS“正在载入”问题是由资源访问或处理问题引起的：硬盘读取速度慢或有坏道：使用CrystalDiskInfo检查硬盘健康状况并更换有问题的硬盘。内存不足：升级内存以满足PS对高分辨率图片和复杂图层处理的需求。显卡驱动程序过时或损坏：更新驱动程序以优化PS和显卡之间的通信。文件路径过长或文件名有特殊字符：使用简短的路径和避免使用特殊字符。PS自身问题：重新安装或修复PS安装程序。

PS启动时一直显示正在载入如何解决？ Apr 06, 2025 pm 06:36 PM

PS启动时卡在“正在载入”可能是由于各种原因造成的：禁用损坏或冲突的插件。删除或重命名损坏的配置文件。关闭不必要的程序或升级内存，避免内存不足。升级到固态硬盘，加快硬盘读取速度。重装PS修复损坏的系统文件或安装包问题。查看错误日志分析启动过程中的错误信息。

PS打开文件时一直显示正在载入如何解决？ Apr 06, 2025 pm 06:33 PM

PS打开文件时出现“正在载入”卡顿，原因可能包括：文件过大或损坏、内存不足、硬盘速度慢、显卡驱动问题、PS版本或插件冲突。解决方法依次为：检查文件大小和完整性、增加内存、升级硬盘、更新显卡驱动、卸载或禁用可疑插件、重装PS。通过逐步排查，并善用PS的性能设置，养成良好的文件管理习惯，可以有效解决该问题。

PS执行操作时一直显示正在载入如何解决？ Apr 06, 2025 pm 06:30 PM

PS卡在“正在载入”？解决方法包括：检查电脑配置（内存、硬盘、处理器）、清理硬盘碎片、更新显卡驱动、调整PS设置、重新安装PS，以及养成良好的编程习惯。

mysql安装后怎么使用 Apr 08, 2025 am 11:48 AM

文章介绍了MySQL数据库的上手操作。首先，需安装MySQL客户端，如MySQLWorkbench或命令行客户端。1.使用mysql-uroot-p命令连接服务器，并使用root账户密码登录；2.使用CREATEDATABASE创建数据库，USE选择数据库；3.使用CREATETABLE创建表，定义字段及数据类型；4.使用INSERTINTO插入数据，SELECT查询数据，UPDATE更新数据，DELETE删除数据。熟练掌握这些步骤，并学习处理常见问题和优化数据库性能，才能高效使用MySQL。

PS羽化如何控制过渡的柔和度？ Apr 06, 2025 pm 07:33 PM

羽化控制的关键在于理解其渐变本质。PS本身不提供直接控制渐变曲线的选项，但你可以通过多次羽化、配合蒙版、精细选区，灵活调整半径和渐变柔和度，实现自然过渡效果。

mysql安装后怎么优化数据库性能 Apr 08, 2025 am 11:36 AM

MySQL性能优化需从安装配置、索引及查询优化、监控与调优三个方面入手。1.安装后需根据服务器配置调整my.cnf文件，例如innodb_buffer_pool_size参数，并关闭query_cache_size；2.创建合适的索引，避免索引过多，并优化查询语句，例如使用EXPLAIN命令分析执行计划；3.利用MySQL自带监控工具(SHOWPROCESSLIST,SHOWSTATUS)监控数据库运行状况，定期备份和整理数据库。通过这些步骤，持续优化，才能提升MySQL数据库性能。

PS卡在载入界面怎么办？ Apr 06, 2025 pm 06:54 PM

PS卡在载入界面可能是由软件自身（文件损坏或插件冲突）、系统环境（驱动过时或系统文件损坏）或硬件（硬盘损坏或内存条故障）问题造成的。首先检查计算机资源是否充足，关闭后台程序释放内存和CPU资源。修复PS安装或检查插件是否存在兼容性问题。更新或回退PS版本。检查显卡驱动并更新，运行系统文件检查。若排除上述问题，则可以尝试硬盘检测和内存测试。

See all articles

Python实现快速排序算法及去重的快速排序的简单示例

热AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

AI Hentai Generator

热门文章

热工具

记事本++7.3.1

SublimeText3汉化版

禅工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

热门话题