这是一种快速排序的实现,比我发现的其他方法更容易理解。尽管此实现似乎没有“就位”,但显然应该进行快速排序。我认为它不在“原地”,因为您要返回一个新数组。
我是否认为此实现“不到位”是正确的?
def quick_sort(sequence):
length = len(sequence)
if length <= 1:
return sequence
else:
pivot = sequence.pop()
items_greater = []
items_lower = []
for item in sequence:
if item > pivot:
items_greater.append(item)
else:
items_lower.append(item)
return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)
This is another implementation I found which I think IS an "in place" version of quick sort. -> https://stackabuse.com/quicksort-in-python/
如果有人可以确认这一点。我会很感激。谢谢!
It is definitely not in place - you are generating new arrays (
items_lower
, etc)不,它不是快速排序算法的“就地”实现。
此实现较容易掌握,但效率很低。请记住,对于您要排序的数组,它会创建一个大小相同的新数组,对于它们的一半,它将创建另一个,然后为一半或另一个,依次类推。 ..您将为大型阵列浪费大量内存。