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邮箱登陆入口在哪里

7444

CakePHP 教程

1371

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

显示更多

Related knowledge

谁得到更多的Python或JavaScript？ Apr 04, 2025 am 12:09 AM

Python和JavaScript开发者的薪资没有绝对的高低，具体取决于技能和行业需求。1.Python在数据科学和机器学习领域可能薪资更高。2.JavaScript在前端和全栈开发中需求大，薪资也可观。3.影响因素包括经验、地理位置、公司规模和特定技能。

distinctIdistinguish有关系吗 Apr 03, 2025 pm 10:30 PM

distinct 和 distinguish 虽都与区分有关，但用法不同：distinct（形容词）描述事物本身的独特性，用于强调事物之间的差异；distinguish（动词）表示区分行为或能力，用于描述辨别过程。在编程中，distinct 常用于表示集合中元素的唯一性，如去重操作；distinguish 则体现在算法或函数的设计中，如区分奇数和偶数。优化时，distinct 操作应选择合适的算法和数据结构，而 distinguish 操作应优化区分逻辑效率，并注意编写清晰可读的代码。

H5页面制作是否需要持续维护 Apr 05, 2025 pm 11:27 PM

H5页面需要持续维护，这是因为代码漏洞、浏览器兼容性、性能优化、安全更新和用户体验提升等因素。有效维护的方法包括建立完善的测试体系、使用版本控制工具、定期监控页面性能、收集用户反馈和制定维护计划。

如何理解 C 语言中的 !x？ Apr 03, 2025 pm 02:33 PM

!x 的理解!x 是 C 语言中的逻辑非运算符，对 x 的值进行布尔取反，即真变假，假变真。但要注意，C 语言中真假由数值而非布尔类型表示，非零视为真，只有 0 才视为假。因此，!x 对负数的处理与正数相同，都视为真。

C语言中 sum 是什么意思？ Apr 03, 2025 pm 02:36 PM

C语言中没有内置的sum函数用于求和，但可以通过以下方法实现：使用循环逐个累加元素；使用指针逐个访问并累加元素；对于大数据量，考虑并行计算。

如何获取58同城工作页面上的实时申请和浏览人数数据？ Apr 05, 2025 am 08:06 AM

如何在爬虫时获取58同城工作页面的动态数据？在使用爬虫工具爬取58同城的某个工作页面时，可能会遇到这样�...

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

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

爱心代码复制粘贴爱心代码免费复制粘贴手机 Apr 04, 2025 am 06:48 AM

复制粘贴代码并非不可行，但需谨慎对待。代码中环境、库、版本等依赖项可能与当前项目不匹配，导致错误或不可预料的结果。务必确保上下文一致，包括文件路径、依赖库和 Python 版本。此外，复制粘贴特定库的代码时，可能需要安装该库及其依赖项。常见的错误包括路径错误、版本冲突和代码风格不一致。性能优化需根据代码原用途和约束重新设计或重构。理解并调试复制的代码至关重要，切勿盲目复制粘贴。

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版

热门话题