的情况下,假设你有这样的快速排序实现,这可能是比标准的一个有一点不同:最好的快速排序变化
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)
只想返回空列表。
这是正确的吗?
我有一种感觉,qsort的这种变化可能会比标准的变化更糟糕,这就是为什么我可能不会使用它,我只是想确保变化的最佳时间复杂度是的确是O(n)。非常感谢你! – Master