h4c*_*k3d 1 language-agnostic sorting algorithm
可能重复: 如何使用合并排序算法进行就地排序？
通常我们使用额外的数组来使用合并排序对其进行排序,是否可以在不使用额外空间的情况下执行此操作？
如果可以,那么合并排序会比快速排序更好吗？
Fre*_*Foo 5
是的,可以执行就地合并排序.这并不意味着它不需要任何额外的内存,因为递归仍然需要O(lg n)堆栈空间(就像quicksort一样).
编辑:我读了Katajainen报纸已经很久了,我从未关注太空复杂性的说法; 显然,合并排序可以在O(1)额外空间中完成.
但不,所有这并不意味着一种算法比另一种算法更好,除非你指定那个词的意思.无论输入如何,随机快速排序虽然可以是二次方的,但仍会执行较小的预期操作次数.哪一个"更好地"用于您的数据取决于从数据统计到程序运行的硬件的各种因素.
归档时间：
13 年，1 月 前
查看次数：
5190 次
最近记录：
12 年 前