Python实现的数据结构与算法之快速排序详解
作者:RussellLuo 发布时间:2022-03-03 16:49:17
标签:Python,快速排序
本文实例讲述了Python实现的数据结构与算法之快速排序。分享给大家供大家参考。具体分析如下:
一、概述
快速排序(quick sort)是一种分治排序算法。该算法首先 选取 一个划分元素(partition element,有时又称为pivot);接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分)、划分元素pivot、right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上;然后分别对left和right两个部分进行 递归排序。
其中,划分元素的 选取 直接影响到快速排序算法的效率,通常选择列表的第一个元素或者中间元素或者最后一个元素作为划分元素,当然也有更复杂的选择方式;划分 过程根据划分元素重排列表,是快速排序算法的关键所在,该过程的原理示意图如下:
<-- 选取划分元素 -->
<-- 划分过程 -->
<-- 划分结果 -->
快速排序算法的优点是:原位排序(只使用很小的辅助栈),平均情况下的时间复杂度为 O(n log n)。快速排序算法的缺点是:它是不稳定的排序算法,最坏情况下的时间复杂度为 O(n2)。
二、Python实现
1、标准实现
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def stdQuicksort(L):
qsort(L, 0, len(L) - 1)
def qsort(L, first, last):
if first < last:
split = partition(L, first, last)
qsort(L, first, split - 1)
qsort(L, split + 1, last)
def partition(L, first, last):
# 选取列表中的第一个元素作为划分元素
pivot = L[first]
leftmark = first + 1
rightmark = last
while True:
while L[leftmark] <= pivot:
# 如果列表中存在与划分元素pivot相等的元素,让它位于left部分
# 以下检测用于划分元素pivot是列表中的最大元素时,
#防止leftmark越界
if leftmark == rightmark:
break
leftmark += 1
while L[rightmark] > pivot:
# 这里不需要检测,划分元素pivot是列表中的最小元素时,
# rightmark会自动停在first处
rightmark -= 1
if leftmark < rightmark:
# 此时,leftmark处的元素大于pivot,
#而rightmark处的元素小于等于pivot,交换二者
L[leftmark], L[rightmark] = L[rightmark], L[leftmark]
else:
break
# 交换first处的划分元素与rightmark处的元素
L[first], L[rightmark] = L[rightmark], L[first]
# 返回划分元素pivot的最终位置
return rightmark
2、Pythonic实现
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def pycQuicksort(L):
if len(L) <= 1: return L
return pycQuicksort([x for x in L if x < L[0]]) + \
[x for x in L if x == L[0]] + \
pycQuicksort([x for x in L if x > L[0]])
对比 标准实现 可以看出,Pythonic实现 更简洁、更直观、更酷。但需要指出的是,Pythonic实现 使用了Python中的 列表解析 (List Comprehension,也叫列表展开、列表推导),每一次 递归排序 都会产生新的列表,因此失去了快速排序算法本来的 原位排序 的优点。
三、算法测试
#!/usr/bin/env python
# -*- coding: utf-8 -*-
if __name__ == '__main__':
L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
M = L[:]
print('before stdQuicksort: ' + str(L))
stdQuicksort(L)
print('after stdQuicksort: ' + str(L))
print('before pycQuicksort: ' + str(M))
print('after pycQuicksort: ' + str(pycQuicksort(M)))
运行结果:
$ python testquicksort.py
before stdQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20]
after stdQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]
before pycQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20]
after pycQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]
希望本文所述对大家的Python程序设计有所帮助。
0
投稿
猜你喜欢
- TFTP文件传输功能:1、获取文件列表2、上传文件3、下载文件4、退出第一部分,TftpServer部分。①导入相关模块from socke
- WTForms 是用于web开发的灵活的表单验证和呈现库,它可以与您选择的任何web框架和模板引擎一起工作,并支持数据验证、CSRF保护、国
- 用python读取视频有两种主要方法,大家可依据自己的需求进行使用。方法一:使用imageio库,没有安装的可用pip安装或自己下载,安装好
- 最近接了一个比较简单的图像处理的单子,花了一点时间随便
- 问题描述利用栈的数据结构实现将十进制数转换成二进制数C语言实现顺序表的存储结构实现栈代码:#include <stdlib.h>
- 实例代码:if __name__ == '__main__': # 时间戳 &nbs
- 一、前言今天我们将用Python来创建一个属于自己的音乐播放器。为此,我们将使用三个软件包:Tkinter:用于UIPygame:播放音乐o
- 即使你没听说过“ * 六度分隔理论”,也很可能听过“凯文 • 贝肯 (Kevin Bacon)的六度分隔值游戏”。在这两个游戏中,目标都是
- 本文实例讲述了Python日期时间Time模块。分享给大家供大家参考,具体如下:关于时间和日期模块python程序能用很多方式处理日期和时间
- 但是Class这个东西,如果用得比较少,充其量只是一个大模块的包装方式. 只有大规模地用它来开发,才能显出它对项目管理的优越性来. 所谓的意
- Django RBAC权限管理概述RBAC(Role-Based Access Control,基于角色的访问控制),通过角色绑定权限,然后
- Python有自己内置的标准GUI库--Tkinter,只要安装好Python就可以调用。今天学习到了图形界面设计的问题,刚开始就卡住了。为
- 近来,越来越多的数据科学家开始使用Python,我不由得想到,尽管他们从pandas、scikit-learn和numpy这些库中得到了不少
- 1、元旦之前受赵晨之邀作为讨论嘉宾参加了ACM组织的“人与信息社会巡讲”。2、去之前赵晨发给了我大致的讨论提纲。咣当了好几下~说实话,我是硬
- 环境Win10Python3.6.6Django2.1.3中间件作用 中间件用于全局修改Django的输入或输出。中间件常见用途 缓存会话认
- 目录瞎比比与 print 相比 logging 有什么优势?基础用法保存到文件多模块使用 logging使用配置文件配置 logging瞎比
- 一、匿名块和命名块◆PL/SQL块分为良好总:命名块和匿名块。◆匿名块:以declare或begin开始,每次执行匿名块都要通过客户端工具将
- 前言sklearn是python的重要机器学习库,其中封装了大量的机器学习算法,如:分类、回归、降维以及聚类;还包含了监督学习、非监督学习、
- 今天用scrapy爬取壁纸的时候(url:http://pic.netbian.com/4kmein...)絮叨了一些问题,记录下来,供后世
- 1、序列(拆包)*用作序列拆包:*可对字符串、列表、集合、元组、字典、数字元素等序列进行拆包print(*(1,2,3,4,5,6))#1