数据结构与算法 10.快速排序 quickSort
2021/10/30 9:09:42
本文主要是介绍数据结构与算法 10.快速排序 quickSort,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序 quickSort
取序列的第一个值作为基点,把序列中比基点小的数和比基点大的数分为两个子序列 把两个子序列分别作为新的序列,再次进行分堆,并不断递归,直至子序列无法再分堆 分堆时取出基点,使用两个指针,从序列的头尾分别向中间移动,移动过程把值与基点作比较 利用基点空出的位置,移动处于错误区域的元素,并利用新空出的位置移动新发现的处于错误区域的元素 需要消耗大量空间 复杂度:最优时间复杂度:O(nlogn) 最差时间复杂度:O(n^2) 稳定性:不稳定
def quick_sort(varlist,start,end) : # 结束递归的条件 if start >= end : return # 取出作为基点的值 mid = varlist[start] # 序列开头和末尾 low = start high = end # 1.第一步:以基点值为界,将整个序列分为,小于基点值和大于基点值的两部分 # 使用两个指针low和high,从序列开头和末尾分别向序列中间移动并取值,将取值与基点值作比较 # low=high时,表示两个指针重叠,即完成了整个序列的比较和分堆,循环结束 while low < high : # 对序列从后向前取值,若取值大于基点值,则继续向前移动high指针并取值 while low < high and varlist[high] >= mid : high -= 1 # 若取值小于基点值,则将取值移动到low指针所在位置,并开始移动low指针 varlist[low] = varlist[high] # 对序列从前向后取值,若取值小于基点值,则继续向后移动low指针并取值 while low < high and varlist[low] < mid : low += 1 # 若取值大于基点值,则将取值移动到high指针所在位置,并开始移动high指针 varlist[high] = varlist[low] # low指针与high指针位置重叠时,把基点值放入该位置 varlist[low] = mid # 2.第二步:把完成分堆的两部分,分别作为一个需要排序的序列,调用自身进行递归 quick_sort(varlist,start,low-1) quick_sort(varlist,high+1,end) varl = [5,1,7,5,6,3,4,8,2,3,5,9] quick_sort(varl,0,len(varl)-1) print(varl) [1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9]
这篇关于数据结构与算法 10.快速排序 quickSort的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享