0

我被要求编写一个“就地”快速排序版本。创建了两个内部函数 - 一个递归函数和一个“就地排序”函数，它选择随机枢轴（需要问题），对列表进行就地排序并在排序后返回枢轴的索引。

     import random

def quicksort(lst):

    def innerfunc(lst, start=0, end=(len(lst) - 1)):   
        temporal_pivot = subfunc(lst, start, end)

        if (end - start > 1): 
            if (temporal_pivot == start or temporal_pivot == start + 1):
                innerfunc(lst, temporal_pivot + 1, end)

            elif (temporal_pivot == end or temporal_pivot == end - 1):
                innerfunc(lst, 0 , temporal_pivot - 1)

            else:
                innerfunc(lst, 0 , temporal_pivot - 1), innerfunc(lst, temporal_pivot + 1, end)


    def subfunc(l, start, end):
        i_random = random.randint(start, end)  # chooses random index!
        l[i_random], l[start] = l[start], l[i_random]

        i_pivot = start
        pivot = l[start]

        i = end
        while i > i_pivot:
            if l[i] <= pivot:
                l.insert(i_pivot, l[i])
                i_pivot += 1
                l.pop(i + 1)

            else:
                i = i - 1

        return i_pivot


    return innerfunc(lst)

问题是运行时间 -

包含 100 个或更多元素的列表的排序非常慢。

你知道如何改进“subfunc”算法和我的快速排序性能吗？

谢谢！

奥伦

4

2 回答 2

2

l.insert()问题是对和的重复调用l.pop()。其中每一个都具有O(n)复杂性，而您希望循环的每次迭代都是O(1).

您需要重新设计该函数，以便它通过交换元素而不是执行重复的插入和删除来工作。

您可以在Wikipedia中找到一些伪代码。

于 2012-12-16T11:58:59.167 回答
0

似乎 subfunc 效率不高 - 循环并插入数组部分。我不是 Python 程序员，但我建议它会导致内存重新分配和成本 O(n) 操作

于 2012-12-16T11:44:58.280 回答