我在算法方面处于中级水平。最近,当我比较不同的排序算法时,这件事一直困扰着我。
当数据是传入而不是已经存在时,您如何比较不同的排序算法?
我自己比较了一些,但不太确定这是否是正确的方法。
插入排序:顾名思义,它为 O(n^2) 复杂度的问题提供了一个很好的解决方案。
堆排序:该技术是为每个推送的数据项构建堆。它对应于复杂度为 O(logn) 的 sift-up 操作,然后将第一个元素与最后一个元素交换,并进行 Heapify 以恢复堆属性。Heapify 又是 O(logn),所以整体复杂度是 O(n logn logn)。但是如果我们已经拥有了所有的数据项,那么它只有 O(n logn),因为我们在构建堆之后只对数据项执行 Heapify 操作。
选择排序:在排序之前需要所有数据项,所以我假设使用选择排序无法解决我们的问题。
树排序:该技术的主要步骤是构建一棵树,其最坏情况时间复杂度为 O(n^2)。然后按顺序遍历就可以了。
我不太确定其他算法。
我正在发布这个问题,因为我正在寻找对这些排序技术的完全掌握。如果您在我的问题或我的比较中发现任何差异,请原谅我。