1

我在算法方面处于中级水平。最近,当我比较不同的排序算法时,这件事一直困扰着我。

当数据是传入而不是已经存在时,您如何比较不同的排序算法?

我自己比较了一些,但不太确定这是否是正确的方法。

插入排序:顾名思义,它为 O(n^2) 复杂度的问题提供了一个很好的解决方案。

堆排序:该技术是为每个推送的数据项构建堆。它对应于复杂度为 O(logn) 的 sift-up 操作,然后将第一个元素与最后一个元素交换,并进行 Heapify 以恢复堆属性。Heapify 又是 O(logn),所以整体复杂度是 O(n logn logn)。但是如果我们已经拥有了所有的数据项,那么它只有 O(n logn),因为我们在构建堆之后只对数据项执行 Heapify 操作。

选择排序:在排序之前需要所有数据项,所以我假设使用选择排序无法解决我们的问题。

树排序:该技术的主要步骤是构建一棵树,其最坏情况时间复杂度为 O(n^2)。然后按顺序遍历就可以了。

我不太确定其他算法。

我正在发布这个问题,因为我正在寻找对这些排序技术的完全掌握。如果您在我的问题或我的比较中发现任何差异,请原谅我。

4

2 回答 2

1

一次构建一个堆项目不会增加任何额外的复杂性(你O(n log n log n)对我来说根本没有意义)。实际上,构建堆的正常方法是无论如何一次向堆中添加一项。也就是说,即使您有所有可用的项目,您也可以先构建前两个的堆,然后添加第三个、第四个,依此类推。如果您一次收到一件物品,则根本不会造成任何额外的工作。就像往常一样,最终结果为 O(N log N)。

需要明确的是:将项目交换到第一个位置然后筛选到树中不是用于添加项目时 - 它是用于删除项目时。也就是说:当您完成将所有项目插入堆中时,您正在读取以产生排序输出。您可以通过将堆底部的项(即数组中的第一项)交换到数组的末尾,然后取出从数组末尾开始的项,并在堆中向上筛选直到堆属性恢复。

当您将新项目添加到堆中时,您将它们添加到最后,然后将它们向下筛选以恢复堆属性。在它们已经全部可用的典型情况下,您可以从数组的开头开始,并在形成堆的项目和仍然只是混乱的项目之间进行分区。要将所有项目构建到一个堆中,您将该分区移动到一个项目上,将该项目向下筛选到它所属的位置,然后重复。对于没有立即提供所有数据的“在线”版本,所有的变化是在您将一个项目筛选到堆中之后,您必须等待下一个项目到达才能将其筛选到堆中(其中您通常会立即插入下一项)。

如果 1) 物品完全有序地到达,并且 2) 你没有意识到这一点,以及 3) 你在构建树时没有重新平衡树,那么构建树只是 O(N 2 )。如果项目开始时的顺序相当随机,即使没有平衡,您的复杂性也将接近 O(N log N)。在构建诸如红黑或 AVL 树之类的典型情况下,即使项目有序,它仍将保持 O(N log N) (尽管如果它们到达,它将是 O(N log N) 且常数较低)以或多或少的随机顺序而不是排序)。同样,如果使用 B 树,即使数据按顺序到达,也会得到 O(N log N) 复杂度。

于 2013-07-15T07:32:14.323 回答
0

插入排序:顾名思义,它为 O(n^2) 复杂度的问题提供了一个很好的解决方案。

我同意,在任何一种情况下都不是那么好。

堆排序:该技术是为每个推送的数据项构建堆。它对应于复杂度为 O(logn) 的 sift-up 操作,然后将第一个元素与最后一个元素交换并 Heapify 以恢复堆属性。Heapify 又是 O(logn),所以整体复杂度是 O(n logn logn)。但是,如果我们已经拥有了所有数据项,那么它只有 O(n logn),因为我们在构建堆之后只对数据项执行 Heapify 操作。

您可以使用最小堆二叉树来执行此操作,但如果您使用的是数组,这可能会很困难。

选择排序:在排序之前需要所有数据项,所以我假设使用选择排序无法解决我们的问题。

在任何一种情况下都很糟糕。

树排序:该技术的主要步骤是构建一棵树,其最坏情况时间复杂度为 O(n^2)。然后按顺序遍历就可以了。

O(nlogn) 如果你使用基数排序。请参阅有关数组的堆排序注释。

其他排序:
计数排序:如果您事先不知道数据,那就太糟糕了。因为你真的不知道你需要多少空间。

基数排序:仍然很神奇,在任何一种情况下都将是最好的排序算法。特别是当您使用字节排序时。您所做的只是在数据进入时输入直方图,然后将其存储到临时链表中。然后进行基数排序。

桶排序:可以采用任何一种方式,比计数排序好得多,不如基数排序。

于 2013-07-15T06:37:20.480 回答