最好的快速排序变化

Question

的情况下，假设你有这样的快速排序实现，这可能是比标准的一个有一点不同：

qsort(list): 
if list is of length 1 or lower - 
    return list 
else - 
    choose a random pivot 
    smaller - get all elements that are smaller than the pivot 
    equal - get all elements that are equal to the pivot, including the pivot itself 
    greater - get all elements that are greater than the pivot 
    return qsort(smaller) + equal + qsort(greater) 

那不是该功能的最好的情况是当函数收到一个所有元素都相同的列表时，那么最佳情况下的时间复杂度就是O(n)，这比快速排序的标准版本的最佳情况时间复杂度更好，即O(n log n)？

造成这种情况的原因在于，该功能只创建这些分区一次，为小和更大的列表将是空的（因为所有的元素都是相同的），这将结束递归，为qsort(smaller)和qsort(greater)只想返回空列表。

这是正确的吗？

Answer 1

是的，在这种情况下，你描述的时间复杂度将是O(n)。

但是，由于需要创建新列表equal，空间也将为O(n)。这种情况更糟，那种排序适当的qsort有一个O(1)（恒定）空间要求。

O(n lg(n))的qsort时间复杂度是一个平均情况，它是假设统计随机数据来计算的。你的改编将有助于在边缘情况下的性能，即所有的值都是相等的，这是不太可能的（尽管你可能对数据有更多的了解）。

如果你正在考虑使用这种算法，而不是标准的qsort，我会建议不要这样做。由于使用额外的列表会增加元素和连接的开销（这种开销取决于列表的实现）。这个开销在qsort中不存在，因为它排序合适。