鱼C论坛

 找回密码
 立即注册
查看: 2253|回复: 2

[已解决]分治算法的快速排序

[复制链接]
发表于 2022-6-13 23:08:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 yayc_zcyd 于 2022-6-13 23:12 编辑
  1. def partition(nums=list):
  2.     pivot = nums[0]
  3.     lo = [x for x in nums[1:] if x < pivot]
  4.     hi = [x for x in nums[1:] if x >= pivot]
  5.     return lo,pivot,hi

  6. def quick_sort(nums=list):
  7.     if len(nums) <= 1:
  8.         return nums
  9.     lo, pivot, hi = partition(nums)
  10.     return quick_sort(lo) + [pivot] + quick_sort(hi)

  11. lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
  12. print(quick_sort(lis))
复制代码
为什么在quick_sort函数里是先运行partition里的lo一套完成后,再运行hi?
  1. return quick_sort(lo) + [pivot] + quick_sort(hi)
复制代码
上面这行代码是什么功能和意思

有没有大佬有能力给我串一遍整个运行流程
最佳答案
2022-6-13 23:33:30
本帖最后由 临时号 于 2022-6-14 00:15 编辑
  1. return quick_sort(lo) + [pivot] + quick_sort(hi)
复制代码

这行运用了递归的思想,将列表的第一个值作为中间值,其他值继续调用quick_sort函数去递归,最后当列表只剩下一个值时返回
程序的执行流程是这样的:
首先,你判断了nums列表的长度
因为现在nums的长度为5,不符合len(nums)<=1的条件,所以程序没有执行return nums
然后你调用了partition函数,将nums列表传了进去
在partition函数中,nums=nums:
首先,你取了nums列表中的第一个值,将其赋值给pivot变量,也就是说此时pivot=0
然后,你创建了一个列表,将nums列表中除了第一个值的其他值并小于pivot的值全部放进去,赋值给lo
也就是说此时lo=[]
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=[3,4,1,2]
然后返回lo,pivot,hi
在quick_sort函数中:
用lo,pivot,hi变量分别接受返回的值
然后调用quick_sort函数,将lo列表传了进去
在quick_sort函数中,nums=lo:
首先,你判断了nums列表的长度
因为现在nums的长度为4,不符合len(nums)<=1的条件,所以程序没有执行return nums
然后你调用了partition函数,将nums列表传了进去
在partition函数中,nums=nums:
首先,你取了nums列表中的第一个值,将其赋值给pivot变量,也就是说此时pivot=3
然后,你创建了一个列表,将nums列表中除了第一个值的其他值并小于pivot的值全部放进去,赋值给lo
也就是说此时lo=[1,2]
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=[4]
然后返回lo,pivot,hi
在quick_sort函数中:
用lo,pivot,hi变量分别接受返回的值
然后调用quick_sort函数,将lo列表传了进去
在quick_sort函数中,nums=lo:
首先,你判断了nums列表的长度
因为现在nums的长度为2,不符合len(nums)<=1的条件,所以程序没有执行return nums
然后你调用了partition函数,将nums列表传了进去
在partition函数中,nums=nums:
首先,你取了nums列表中的第一个值,将其赋值给pivot变量,也就是说此时pivot=1
然后,你创建了一个列表,将nums列表中除了第一个值的其他值并小于pivot的值全部放进去,赋值给lo
也就是说此时lo=[]
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=[2]
然后返回lo,pivot,hi
在quick_sort函数中:
用lo,pivot,hi变量分别接受返回的值
然后调用quick_sort函数,将lo列表传了进去
在quick_sort函数中,nums=lo:
首先,你判断了nums列表的长度
因为现在nums的长度为0,符合len(nums)<=1的条件,所以程序执行return nums
这就是第一次调用quick_sort(lo)的执行过程,quick_sort(hi)同理
太多了,我就不写了
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2022-6-13 23:33:30 | 显示全部楼层    本楼为最佳答案   
本帖最后由 临时号 于 2022-6-14 00:15 编辑
  1. return quick_sort(lo) + [pivot] + quick_sort(hi)
复制代码

这行运用了递归的思想,将列表的第一个值作为中间值,其他值继续调用quick_sort函数去递归,最后当列表只剩下一个值时返回
程序的执行流程是这样的:
首先,你判断了nums列表的长度
因为现在nums的长度为5,不符合len(nums)<=1的条件,所以程序没有执行return nums
然后你调用了partition函数,将nums列表传了进去
在partition函数中,nums=nums:
首先,你取了nums列表中的第一个值,将其赋值给pivot变量,也就是说此时pivot=0
然后,你创建了一个列表,将nums列表中除了第一个值的其他值并小于pivot的值全部放进去,赋值给lo
也就是说此时lo=[]
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=[3,4,1,2]
然后返回lo,pivot,hi
在quick_sort函数中:
用lo,pivot,hi变量分别接受返回的值
然后调用quick_sort函数,将lo列表传了进去
在quick_sort函数中,nums=lo:
首先,你判断了nums列表的长度
因为现在nums的长度为4,不符合len(nums)<=1的条件,所以程序没有执行return nums
然后你调用了partition函数,将nums列表传了进去
在partition函数中,nums=nums:
首先,你取了nums列表中的第一个值,将其赋值给pivot变量,也就是说此时pivot=3
然后,你创建了一个列表,将nums列表中除了第一个值的其他值并小于pivot的值全部放进去,赋值给lo
也就是说此时lo=[1,2]
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=[4]
然后返回lo,pivot,hi
在quick_sort函数中:
用lo,pivot,hi变量分别接受返回的值
然后调用quick_sort函数,将lo列表传了进去
在quick_sort函数中,nums=lo:
首先,你判断了nums列表的长度
因为现在nums的长度为2,不符合len(nums)<=1的条件,所以程序没有执行return nums
然后你调用了partition函数,将nums列表传了进去
在partition函数中,nums=nums:
首先,你取了nums列表中的第一个值,将其赋值给pivot变量,也就是说此时pivot=1
然后,你创建了一个列表,将nums列表中除了第一个值的其他值并小于pivot的值全部放进去,赋值给lo
也就是说此时lo=[]
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=[2]
然后返回lo,pivot,hi
在quick_sort函数中:
用lo,pivot,hi变量分别接受返回的值
然后调用quick_sort函数,将lo列表传了进去
在quick_sort函数中,nums=lo:
首先,你判断了nums列表的长度
因为现在nums的长度为0,符合len(nums)<=1的条件,所以程序执行return nums
这就是第一次调用quick_sort(lo)的执行过程,quick_sort(hi)同理
太多了,我就不写了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-6-14 08:20:31 | 显示全部楼层
临时号 发表于 2022-6-13 23:33
这行运用了递归的思想,将列表的第一个值作为中间值,其他值继续调用quick_sort函数去递归,最后当列表只剩 ...

谢谢!
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-2 00:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表