一次排序数字与每个数字排序

问题描述 投票:1回答:2

是否有任何一种算法在时间复杂度方面受益,将每个项目在生成时按排序顺序排列到列表中,而不是生成整个列表并仅对完全未排序的成品使用quicksort?

我在想不,因为如果是那样的话,那么您可以使用此算法遍历未排序的列表以击败快速排序,但我想知道自己是否错了。

algorithm sorting time-complexity
2个回答
1
投票

由于您是指在时间复杂度上击败快速排序,所以我假设问题仅涉及基于比较的排序算法。如果您包括基于非比较的排序,则存在几种O(n)算法。

存在诸如插入排序之类的算法,如果前几个元素已被排序,则可以及时受益。但是,它们是否与快速排序进行比较将取决于数组的长度以及要排序的元素数量。可以说有n个排序的元素,我们又添加了1个。那么快速排序将是O(nlogn),插入排序将是O(n)。

要将1个元素添加到已排序的数组中,我们不能少于O(n),因为我们需要与其他所有元素进行比较。

但是,如果您要迭代执行此操作,则为(对于n个元素)

O(1)+O(2)+O(3)+....+O(n) = O(n^2)

迭代地,迭代的时间复杂度最终使算法变慢。

您还需要注意,如果大多数数组已经排序,则快速排序将开始采用复杂度O(n ^ 2)。因此,诸如归类排序(再次为O(nlogn))之类的算法将在时间复杂度方面胜过它。

而且,已经证明基于比较的排序不能小于O(nlogn)。因此,试图击败它毫无意义。


0
投票

如果您不坚持使用列表,那么二叉搜索树的插入复杂度为O(log(n)),并且在插入结束之前会保持顺序。但是,这会产生开销,因此仅当您绝对需要在每次插入后知道元素的排序顺序时才使用此方法。

假设您需要在每次插入后找到插入元素的索引。请注意,在排序列表中插入所需索引将花费O(n),因为您必须向右移动更大的元素才能腾出空间。

© www.soinside.com 2019 - 2024. All rights reserved.