QuickSort算法

Question

这是我实现的快速排序算法：

def quick_sort(sequence):
    if len(sequence)<= 1:
        return sequence
    else:
        pivot = sequence.pop() # To take the last item of "sequence" list
    
    greater =[]  
    lower = []
       
    for n in sequence:
        if n > pivot : 
            greater.append(n)
        else:
            lower.append(n)

""" return the quiqk sorted "lower" and "greater" lists ,and pivot as a list in between """
    return quick_sort[lower] + [pivot] + quick_sort[greater]

如何改进?

Answer 1

1. 就地快速排序: 您可以在其中进行快速排序，以便它只使用O(log(N))内存或O(1)内存。内存是指您的函数使用多少计算机数据(与速度不同)。
2. 选择更好的枢轴: 选择最后一个元素作为枢轴将使快速排序收敛到排序列表的O(N平方)，这在现实场景中很常见。O(N平方)非常非常慢，所以你绝对不想选择最后一个元素作为你的枢轴。下面是一些您可以考虑的支点：
   • 列表中的中间元素。如果您选择这一点，您将不会得到O(N平方)时间，几乎排序的列表，但它仍然很容易作出一个列表，使您的程序进入O(N平方)的时间复杂性。我不推荐这个，虽然它仍然比你现在的更好。
   • Mo3方法。在这里，您的枢轴是列表的第一个、第二个和最后一个元素的中间值。尽管仍有可能，但不太可能接近O(N平方)的时间复杂度。由于3的中位数仍然比较容易计算，所以您一定要考虑这一点。
   • 列表中的随机元素。您可以通过导入随机random.choice(序列)从列表中选择一个随机元素，选择一个随机变量将使O(N^2)时间变得几乎不可能。然而，寻找一个随机变量需要花费一些时间(Mo3更快，但它可能会变得非常慢)。

3. 插入排序对于大小小于10的列表，请使用插入排序对列表的其余部分进行排序。插入排序，尽管O(N平方)时间复杂度，比对10或更小的列表的快速排序要快。您可以将其实现到代码中，如: def quick_sort(序列)：if len(序列) <= 10:插入排序( sequence )返回序列，请记住，您必须实现插入排序。如果您还不知道插入排序是什么，我建议使用https://www.geeksforgeeks.org/insertion-sort/。