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

yayc_zcyd

def partition(nums=list):
    pivot = nums[0]
    lo = [x for x in nums[1:] if x < pivot]
    hi = [x for x in nums[1:] 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) + [pivot] + quick_sort(hi)

lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quick_sort(lis))

为什么在quick_sort函数里是先运行partition里的lo一套完成后，再运行hi？

return quick_sort(lo) + [pivot] + quick_sort(hi)

上面这行代码是什么功能和意思

有没有大佬有能力给我串一遍整个运行流程

最佳答案

月排行榜 / 总排行榜

临时号

2022-6-13 23:33:30

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)同理
太多了,我就不写了

跳转到最佳答案楼层

临时号

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)同理
太多了,我就不写了

yayc_zcyd

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

谢谢！