分治算法的快速排序
本帖最后由 yayc_zcyd 于 2022-6-13 23:12 编辑def partition(nums=list):
pivot = nums
lo = if x < pivot]
hi = if x >= pivot]
return lo,pivot,hi
def quick_sort(nums=list):
if len(nums) <= 1:
return nums
lo, pivot, hi = partition(nums)
return quick_sort(lo) + + quick_sort(hi)
lis =
print(quick_sort(lis))为什么在quick_sort函数里是先运行partition里的lo一套完成后，再运行hi？{:10_262:}
return quick_sort(lo) + + quick_sort(hi)上面这行代码是什么功能和意思{:10_266:}
有没有大佬有能力给我串一遍整个运行流程{:9_221:}
本帖最后由 临时号 于 2022-6-14 00:15 编辑
return quick_sort(lo) + + 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=
然后返回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=
然后,你又创建了一个列表,将nums列表中除了第一个值的其他值并大于等于pivot的值全部放进去,赋值给hi
也就是说此时hi=
然后返回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=
然后返回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)同理
太多了,我就不写了 临时号 发表于 2022-6-13 23:33
这行运用了递归的思想,将列表的第一个值作为中间值,其他值继续调用quick_sort函数去递归,最后当列表只剩 ...
谢谢！{:10_281:}
页:
[1]