我必须用我选择的语言为家庭作业实现 QuickSort 算法,我选择了 Python。
在讲座中,我们被告知 QuickSort 是内存高效的,因为它在原地工作;即,它没有用于递归的输入数组部分的额外副本。
考虑到这一点,我尝试在 Python 中实现 QuickSort 算法,但不久之后我意识到,为了编写一段优雅的代码,我必须在递归时将部分数组传递给函数本身。由于每次执行此操作时 Python 都会创建新列表,因此我尝试使用 Python3(因为它支持 nonlocal 关键字)。以下是我的注释代码。
def quicksort2(array):
# Create a local copy of array.
arr = array
def sort(start, end):
# Base case condition
if not start < end:
return
# Make it known to the inner function that we will work on arr
# from the outer definition
nonlocal arr
i = start + 1
j = start + 1
# Choosing the pivot as the first element of the working part
# part of arr
pivot = arr[start]
# Start partitioning
while j <= end:
if arr[j] < pivot:
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i += 1
j += 1
temp = arr[start]
arr[start] = arr[i - 1]
arr[i - 1] = temp
# End partitioning
# Finally recurse on both partitions
sort(start + 0, i - 2)
sort(i, end)
sort(0, len(array) - 1)
现在,我不确定自己是否做得很好,还是遗漏了什么。我已经编写了一个更 Pythonic 版本的 QuickSort,但它肯定不能就地工作,因为它不断返回输入数组的部分并将它们连接起来。
我的问题是,这是在 Python 中执行此操作的方式吗?我搜索了 Google 和 SO,但没有找到真正的 QuickSort 就地实现,所以我认为最好问问。
最佳答案
当然不是最好的方法,加上这个著名的算法会有几十个完美的实现..这是我的,很容易理解
def sub_partition(array, start, end, idx_pivot):
'returns the position where the pivot winds up'
if not (start <= idx_pivot <= end):
raise ValueError('idx pivot must be between start and end')
array[start], array[idx_pivot] = array[idx_pivot], array[start]
pivot = array[start]
i = start + 1
j = start + 1
while j <= end:
if array[j] <= pivot:
array[j], array[i] = array[i], array[j]
i += 1
j += 1
array[start], array[i - 1] = array[i - 1], array[start]
return i - 1
def quicksort(array, start=0, end=None):
if end is None:
end = len(array) - 1
if end - start < 1:
return
idx_pivot = random.randint(start, end)
i = sub_partition(array, start, end, idx_pivot)
#print array, i, idx_pivot
quicksort(array, start, i - 1)
quicksort(array, i + 1, end)
好的,首先是分区子例程的单独函数。它需要数组, 感兴趣的起点和终点,以及枢轴的索引。这个功能应该清楚
Quicksort 然后在整个数组上第一次调用分区子程序;然后 递归地调用自身以将所有内容排序到枢轴以及之后的所有内容。
不懂就问
关于python - Python 中的就地快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17773516/