使用就地排序进行快速排序

2024-03-29 11:40:49 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试用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:])

Tags: 代码inforlenif排序defrange
1条回答
网友
1楼 · 发布于 2024-03-29 11:40:49

您的代码试图就地排序,但它会将切片副本传递给递归调用,因此您只需就地排序这些副本,然后丢弃它们。你知道吗

(如果不清楚:切片列表总是复制列表。更复杂的类型,如memoryviewnp.array,可能支持对其结构的一部分进行“共享视图”,但列表故意很简单。)


解决此问题的一种方法是更改为复制排序,而不是就地排序,其结果可能是:

return quickSort(ar[:wall]) + ar[wall] + quickSort(ar[wall+1:])

(当然,您还需要更改上面的琐碎代码来构建副本,而不是原地乱序)


另一种方法是通过传递列表本身和切片索引(而不是列表的切片副本)保持原位:

def quickSort(ar, start=None, stop=None):
    if start is None: start = 0
    if stop is None: stop = len(ar)

    pivot = ar[stop-1]
    for i in range(start, (stop-start)-2):

    # and so on

    quickSort(ar, start, wall)
    quickSort(ar, wall+1, stop)

一定要挑一个或另一个——一部分到位,一部分复制和组装的分类是一个大烂摊子。你知道吗

相关问题 更多 >