我正在尝试用python编写使用就地排序的快速排序代码。我的代码在子数组中工作得很好,但是它似乎不能将子数组粘在一起形成最终的排序数组。你知道吗
def quickSort (ar):
if len(ar)>1:
pivot = ar[-1]
wall = 0
for i in range(len(ar)-2):
if ar[i] <= pivot:
ar[wall], ar[i] = ar[i], ar[wall]
wall += 1
ar[wall], ar[-1] = ar[-1], ar[wall]
quickSort (ar[:wall])
quickSort (ar[wall+1:])
您的代码试图就地排序,但它会将切片副本传递给递归调用,因此您只需就地排序这些副本,然后丢弃它们。你知道吗
(如果不清楚:切片列表总是复制列表。更复杂的类型,如
memoryview
或np.array
,可能支持对其结构的一部分进行“共享视图”,但列表故意很简单。)解决此问题的一种方法是更改为复制排序,而不是就地排序,其结果可能是:
(当然,您还需要更改上面的琐碎代码来构建副本,而不是原地乱序)
另一种方法是通过传递列表本身和切片索引(而不是列表的切片副本)保持原位:
一定要挑一个或另一个——一部分到位,一部分复制和组装的分类是一个大烂摊子。你知道吗
相关问题 更多 >
编程相关推荐