快速排序算法是分治法的经典应用,具有非常高的效率。
import random
def quickSort(x, start, end):
if start >= end:
return
i = start
j = end
# 使用第一个元素作为枢点
key = x[start]
while i # 从后向前寻找第一个比指定元素小的元素
while iand x[j]>=key:
j -= 1
x[i] = x[j]
# 从前向后寻找第一个比指定元素大的元素
while iand x[i]<=key:
i += 1
x[j] = x[i]
x[i] = key
# 递归,分治
quickSort(x, start, i-1)
quickSort(x, i+1, end)
for i in range(100000):
# 生成随机测试数据
x = [random.randint(1,100) for i in range(20)]
y = sorted(x)
quickSort(x, 0, len(x)-1)
if x!=y:
print('error')
运行无输出,说明代码正确,与Python内置排序函数sorted()结果一致。
----------相关阅读----------
Python按位异或运算符^应用案例一则:查找只出现一次的数字
三种Fibonacci数列第n项计算方法及其优劣分析
Python快速计算Fibonacci数列中第n项的方法
Python版组合数计算方法优化思路和源码
Python组合列表中多个整数得到最小整数(一个算法的巧妙实现)
Python编写人机对战小游戏(抓小狐狸)
Python寻找给定序列中相差最小的两个数字
几行Python代码模拟轮盘抽奖游戏
Python使用递归法对整数进行因数分解
Python模拟大整数乘法的小学竖式计算过程
基于非递归算法的汉诺塔游戏之Python实现
Python计算有向图节点的入度和出度
Python使用广度优先和深度优先两种方法遍历目录树
Python使用筛选法计算小于给定数字的所有素数
哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)
Python版堆排序算法
Python版归并排序算法(附Python程序__name__属性用法演示视频)
Python模拟汉诺塔问题移动盘子的过程
Python版双链表结构与有关操作
侏儒排序算法原理与Python实现
Python实现单链表
Python版基于递归的冒泡排序算法
Python版快速排序算法
Python版选择排序算法
Python版冒泡法排序算法
Python计算整数阶乘的几种方法比较
鸡兔同笼问题新解与Python实现
Pythonic:递归、回溯等5种方法生成不重复数字整数
一维序列卷积之Python实现
祝所有程序员1024节日快乐
学会提问,你就成功了一大半!
盘点那些让人上火的提问方式(论如何让交流更高效)
----------喜大普奔----------
1、继《Python程序设计基础》(2017年9月第5次印刷)、《Python程序设计(第2版)》(2017年9月第4次印刷)、《Python可以这样学》(2017年7月第3次印刷)系列图书之后,董付国老师新书《Python程序设计开发宝典》已于2017年8月1日在清华大学出版社出版,并于2017年9月进行了第2次印刷。为庆祝新书《Python程序设计开发宝典》全面上架,清华大学出版社联合“赣江图书专营”淘宝店推出特价优惠活动,《Python程序设计开发宝典》原价69元,新书上架期间超低价39.8元,可以复制下面的链接使用浏览器打开查看图书详情和购买:
https://detail.tmall.com/item.htm?spm=a1z10.3-b-s.w4011-14464369246.84.46f16db0roWfX4&id=557107249812&rn=339cbc9df2bac424664103917dedfbd2&abbucket=8&tbpm=3
2、董付国老师新作《中学生可以这样学Python》已正式出版,很快就会在各大书城全面上架。
3、董付国老师6本Python系列图书阅读指南