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


猜你喜欢
- 一、获取Tensor神经网络在运算过程中实际上是以Tensor为格式进行计算的,我们只需稍稍改动一下forward函数即可从运算过程中抓到T
- 现在公布方法:替换editor.js 函数 // Toolbar button onmouseup
- 日常在网站使用过程中经常遇到图形验证,今天准备自己做个图形验证码,这算是个简单的功能,也适合新手练习的,便于自己学习。 主要用到的库--PI
- 上传html文件内容如下:操作步骤<html><head><meta http-equiv="con
- Python 是一种美丽的语言,它简单易用却非常强大。但你真的会用 Python 的所有功能吗?任何编程语言的高级特征通常都是通过大量的使用
- ROW_NUMBER()函数将针对SELECT语句返回的每一行,从1开始编号,赋予其连续的编号。在查询时应用了一个排序标准后,只有通过编号才
- 问题所在:当我们想让应用层和http之间的所有接口都采用json,这样,客户端代码就可以纯碎用javascript的对象来编写,服务器打啊也
- 前言:最近写爬虫会经常遇到一些验证码识别的问题,现如今的验证码已经是五花八门,刚开始的验证码就是简单的对生成的验证码图片进行一些干扰,但是随
- 当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多个for循环嵌套,但是这样做有一些缺点,那就是效率太低、而且有多少层
- PDO::_constructPDO::_construct — 创建一个表示数据库连接的 PDO 实例(PHP 5 >= 5.1.0
- 实例如下所示:<?php索引数组//数组第一种定义 $arr = array(1,2,3);var_dump($arr); //数组第
- 每个JavaScript函数都有prototype属性(javascript对象没有这个属性),这个属性引用了一个对象,这个对象就是原型对象
- Oracle的show processlistset linesize 400;set pagesize 400;col sql_text
- 前言在学习Flask框架的蓝图时,遇到导包时用到了`from . 模块 import 对象`,然后试了试直接 import会报错,直接告诉我
- 建立连接在WPF当中,需要为View与ViewModel建立连接, 我们需要找到View的DataContext, 如下所示:建立连接的方式
- 以前一直用RHEL 6.3和6.4,系统盘里自带了mysql server,配置好yum源后,直接yum install mysql-ser
- 概述Go 语言中的 new 和 make 一直是新手比较容易混淆的东西,咋一看很相似。不过解释两者之间的不同也非常容易。new 的主要特性首
- golang常用库之-pkg/errors包背景golang自带了错误信息包error只提供了简单的用法, 如errors.New(),和e
- 这是今天在温习lambda表达式的时候想到的问题,众所周知C系列语言中的 三元运算符(?:)是一个非常好用的语句,关于C中的三元运算符表达式
- flags参数re.I IGNORECASE 忽略字母大小写re.L &nb