快速排序主函数的return

来源:1-3 第一版快速排序法

讲武德的年轻人

2021-08-19 23:42:29

老师好!我有个关于快速排序主函数中是否应该加return的问题(下面是我的python code)。您在视频中没有return,我理解,在python中,数组list是mutable type,所以不需要return原数组?但是,我的程序中,如果不加入```return nums```,返回的却是一个None; 加入了return nums,才能正确返回sorted list。


我不确定问题出在哪里?能否请您点拨一二?谢谢!

def QuickSort(nums, l, r):
if l >= r:
return None

p = Partition(nums, l, r)

QuickSort(nums, l, p-1)
QuickSort(nums, p+1, r)
return nums



def Partition(nums, l, r):

marker = nums[l]
j = l

for k in range(j+1,r+1):
if nums[k] <= marker:
j += 1
nums[k], nums[j] = nums[j], nums[k]
nums[l], nums[j] = nums[j], nums[l]

return j


写回答

1回答

liuyubobobo

2021-08-20

是的,课程中的快速排序是原地排序。原地排序的意思就是,不是通过返回值来得到排序结果,而是直接在传入的 nums 参数中进行操作,得到排序结果。


Python 里同理,返回值虽然是 None,但你可以打印输出一下经过快排函数的 nums,应该已经排好序了。


你当然可以做成“不修改原数组,返回一个排好序的新数组的快速排序”,其实很简单,把传来 nums 先做一份拷贝 nums_copy,然后对 nums_copy 做原地块排,返回 nums_copy 就好。


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2610 学习 · 1087 问题

查看课程