Python实现快速排序的方法详解
作者:鲸落丶 发布时间:2022-08-29 13:08:35
标签:Python,快速排序
本文实例讲述了Python实现快速排序的方法。分享给大家供大家参考,具体如下:
说起快排的Python实现,首先谈一下,快速排序的思路:
1、取一个参考值放到列表中间,初次排序后,让左侧的值都比他小,右侧的值,都比他大。
2、分别对左侧和右侧的部分递归第1步的操作
实现思路:
两个指针left,right分别指向列表的第一个元素和最后一个元素,然后取一个参考值,默认为第一个列表的第一个元素list[0],称为K
然后left指向的值先和参考值K进行比较,若list[left]小于或等于K值,left就一直向右移动,left+1,直到移动到大于K值的地方,停住
right指向的值和参考值K进行比较,若list[right]大于K值,right就一直向左移动,right-1,直到移动到小于K值的地方,停住
此时,left和right若还没有相遇,即left还小于right,则二者指向的值互换
若已经相遇则说明,第一次排序已经完成,将list[right]与list[0]的值进行互换,进行之后的递归
编程实现:
#快排的主函数,传入参数为一个列表,左右两端的下标
def QuickSort(list,low,high):
if high > low:
#传入参数,通过Partitions函数,获取k下标值
k = Partitions(list,low,high)
#递归排序列表k下标左侧的列表
QuickSort(list,low,k-1)
# 递归排序列表k下标右侧的列表
QuickSort(list,k+1,high)
def Partitions(list,low,high):
left = low
right = high
#将最左侧的值赋值给参考值k
k = list[low]
#当left下标,小于right下标的情况下,此时判断二者移动是否相交,若未相交,则一直循环
while left < right :
#当left对应的值小于k参考值,就一直向右移动
while list[left] <= k:
left += 1
# 当right对应的值大于k参考值,就一直向左移动
while list[right] > k:
right = right - 1
#若移动完,二者仍未相遇则交换下标对应的值
if left < right:
list[left],list[right] = list[right],list[left]
#若移动完,已经相遇,则交换right对应的值和参考值
list[low] = list[right]
list[right] = k
#返回k值
return right
list_demo = [6,1,2,7,9,3,4,5,10,8]
print(list_demo)
QuickSort(list_demo,0,9)
print(list_demo)
运行结果:
[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
希望本文所述对大家Python程序设计有所帮助。
来源:https://www.cnblogs.com/kunpengv5/p/7833361.html
0
投稿
猜你喜欢
- 本文实例讲述了python定时器(Timer)用法。分享给大家供大家参考。具体如下:# encoding: UTF-8import thre
- 大家好,今天我们要看看如何用 Python制作音乐播放器。此音乐播放器播放您的歌曲,您可以在播放歌曲时暂停、恢复、设置音量,然后您可以停止音
- 这些帖子将分为三个部分。1.密码验证功能2.重构密码验证函数3.对密码验证功能进行单元测试这是Python系列中自定义密码验证的第三部分,也
- 这是早上找了点时间写了一个利用404错误达到静态态效果的类,准备在HTTP://PJSKIN.MYSUC.COM中使用的。不过现在没时间去弄
- 如果说哪个开源程序不需要介绍大家就认识,那一定是phpMyAdmin,一款流行的MySQL数据库的Web管理界面。MySQL是全球最流行的W
- 如下所示:import numpy as np arr = [1,2,3,4,5,6]#求均值arr_mean = np.mean(arr)
- by yemoo有时在编写网页代码时发现,img底部莫名奇妙多出大约3px的空白,无论怎么调节css都不可以,今天再次遇到此问题,网上看了一
- FileSystemObject、Folder 和 File 对象的一些方法都与通过 TextStream 对象创建、读取或写入文件有关。虽
- 1.触发器概述触发器是SQL Server数据库应用中一个重要工具,是一种特殊类型的存储过程,应用非常广泛。一般存储过程主要通过存储过程名而
- 我就废话不多说了,直接上代码吧!集成环境:win10 pycharm #!/usr/bin/env python3.5.2# -*- cod
- 代理模式的优点代理模式可以保护原对象,控制对原对象的访问;代理模式可以增强原对象的功能,通过代理对象来添加一些额外的功能;代理模式可以提高系
- 代码如下:<% '/* 函数名称:Zxj_ReplaceHtmlClearHtml '/
- 一个简单的例子:将如下代码另存为.wsc文件,并右键“注册”(卸载时右键“不注册”)。<Component> <regis
- 一、卷积神经网络卷积神经网络(ConvolutionalNeuralNetwork,CNN)最初是为解决图像识别等问题设计的,CNN现在的应
- 当where子句对某一列使用函数时,除非利用这个简单的技术强制索引,否则Oracle优化器不能在查询中使用索引。通常情况下,如果在WHERE
- 前言VScode是一个相当优秀的IDE,具备开源、跨平台、模块化、插件丰富、启动时间快、颜值高、可高度定制等等优秀的特质,不愧是微软爸爸的私
- 现在同类型的网站数不胜数,网站的功能或服务日趋同质化,大的方面看不出什么差别,差别就体现在细节上。“窥斑见豹”,细节成为网站最有力的表现形式
- 函数getcache,会自动建立需要的缓存。 代码如下:Function getcache(funsname,isreset,is
- 目录简单的验证码简单的登录页面我们经常在登录一个网站,或者注册的时候需要输入一个验证码,有时候觉得很烦,因为有些验证码不仅复杂还看不清,许多
- Eric A. Meyer 对基于 Web 标准的 CSS 与 HTML 绝非一知半解,他是这个领域杰出的专家,曾写过不少 CSS 方面的书