python递归实现快速排序
作者:data_heng 发布时间:2023-08-26 22:46:27
标签:python,递归,快速排序
快速排序(QuickSort)是对冒泡排序的一种改进:
基本思想:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序
过程可以递归进行,以此达到整个数据变成有序序列。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,
进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
利用python实现的快速排序代码quick_sort.py如下:
def sub_sort(array,low,high):
pivotkey=array[low]
while low<high :
while low<high and array[high]>=pivotkey:
high -= 1
array[low]=array[high]
while low<high and array[low]<=pivotkey:
low += 1
array[high]=array[low]
array[low]=pivotkey
return low
def quick_sort(array,low,high):
if low < high :
pivoloc=sub_sort(array,low,high)
quick_sort(array,low,pivoloc-1)
quick_sort(array,pivoloc+1,high)
if __name__=="__main__":
array=[49,38,65,97,76,13,27]
print array
quick_sort(array,0,len(array)-1)
print array
对一个数组array=[49, 38, 65, 97, 76, 13, 27]进行快速排序,得到的结果如下所示:
=============== RESTART: I:\python_DataStructure\quick_sort.py ===============
[49, 38, 65, 97, 76, 13, 27]
[13, 27, 38, 49, 65, 76, 97]
>>>
来源:https://blog.csdn.net/zhoufen12345/article/details/53560172
0
投稿
猜你喜欢
- 最终效果如下图,右侧灰边看相对位置,版权所有谨防假冒:去年曾针对有时间先后的翻页记录了思考片段。之后没来得及调整一直是默认和插件并用,虽然难
- 阅读上一章:Chapter 10 应用CSSChapter 11 打印样式先前在第10章中,讨论了几种为文档应用CSS的方法,这一章是要研究
- eWebEditor在线HTML编辑助手是基于eWebEditor在线HTML编辑器的扩展工具。当您的电脑安装了eWebEditor在线HT
- 时候难免需要直接调用Shell命令来完成一些比较简单的操作,比如mount一个文件系统之类的。那么我们使用Python如何调用Linux的S
- 项目介绍go-admin 是一个中后台管理系统,基于(gin, gorm, Casbin, Vue, Element UI)实现。主要目的是
- 网站中很多表单都会用到上传图片,logo,照片,用户也会上传图片,这个时候网站就需要一个上传图片的功能,而且在上传后希望能预览一下看上传的对
- 1.1.1 摘要 如果说要对数据库进行优化,我们主要可以通过以下五种方法,对数据库系统进行优化。 1. 计算机硬件调优 2. 应用程序调优
- 近日,有朋友一直打听flash连结服务器相关的知识,搞得我忧心重重,重点是自己也忘记了,大部分Flash的相关开发都是两年前的事,而且fla
- Delphi连接MySQL真麻烦,研究了一天,从网上找了无数文章,下载了无数插件都没解决。最后返璞归真,老老实实用ADO来连接,发现也不是很
- 问题:连续或者单个窗体,如何打印当前显示的记录?当前窗体还有对应的子窗体,也要一起打印出来我在一个窗体里有一个单号,大子窗体里有几组数据,我
- 1、设置数据库模式为简单模式:打开SQL企业管理器,在控制台根目录中依次点开Microsoft SQL Server-->SQL Se
- 一、Flask蓝图目录我们之前写的Flask项目都是自己组织的目录结构,其实Flask官方有其推荐的目录结构,以下就是一个符合官方推荐的Fl
- 操作系统:Windows2000,IIS5出现症状:使用ASPJPEG时执行Server.CreateObject("Persit
- 现在网页设计师除了把页面做的漂亮以外,越来越注重“用户体验”,就是要做“别让用户思考”的网页,使网站真正做到“可用性”。望望结合几年的工作经
- 最近Google Code推出了一个面向网站开发者的 * Google DocType。它来自于网站开发者同时又面
- 1。在Asp页面首部<head>加入 Response.Buffer =
- 好多网友问起来,·深度学习网址导航·深度学习整站系统 的后台管理能否增加批量删除功能,如何加:就是列出N篇文章或网址信息,每篇文章或网址前有
- 这个间歇性向上滚动js代码很适合做广告展示,友情链接等等。与平常的无缝向上连续滚动不同的是它每滚动一个就会停顿一会儿。<!DOCTYP
- 在windows操作系统上使用IE作为浏览器时。常常会发生这样的问题:在浏览使用UTF-8编码的网页时,浏览器无法自动侦测(即没有设定“自动
- 数据库系统的安全性包括很多方面。由于很多情况下,数据库服务器容许客户机从网络上连接,因此客户机连接的安全对MySQL数据库安全有很重要的影响