algorithm - 使用红黑树进行排序

Question

在 红黑树 上插入的最坏情况运行时间是 O(lg n) 如果我执行 in-order walk 在树上，我基本上访问了每个节点，因此打印排序集合的最坏情况总运行时间为 O(n lg n)

我很好奇，为什么 red-black trees 不是 quick sort 的首选排序对象(其平均运行时间是 O(n lg n )。

我看到这可能是因为 红黑树 没有就地排序，但我不确定，所以也许有人可以提供帮助。

Answer 1

了解哪种排序算法性能更好实际上取决于您的数据和情况。

如果您谈论的是一般/实用术语，

快速排序(您随机选择一个枢轴/只选择一个固定的枢轴，使最坏情况为 Omega(n^2))可能比红黑树更好，因为(不一定按重要性排序)

• 就地快速排序。这使您的内存占用量很小。假设这个快速排序例程是处理大量数据的程序的一部分。如果您继续使用大量内存，您的操作系统可能会开始交换您的进程内存并破坏您的性能。

• Quicksort 内存访问是本地化的。这与缓存/交换配合得很好。

• Quicksort 可以很容易地并行化(这些天可能更相关)。

• 如果您尝试使用数组来优化二叉树排序(使用没有平衡的二叉树)，您最终会做类似快速排序的事情!

• 红黑树有内存开销。您可能必须多次分配节点，树的内存需求是使用数组的两倍/三倍。

• 排序后，假设您想要第 1045 个(比方说)元素，您将需要在树中维护顺序统计信息(因此需要额外的内存成本)并且您的访问时间为 O(logn)!

• 红黑树有开销只是为了访问下一个元素(指针查找)

• 红黑树不能很好地处理缓存，指针访问可能会导致更多交换。

• 红黑树中的旋转会增加 O(nlogn) 中的常数因子。

• 也许最重要的原因(但如果您有可用的库等则无效)，Quicksort 非常易于理解和实现。连小学生都能听懂!

我会说你尝试衡量这两种实现，看看会发生什么!

另外，Bob Sedgewick 写了一篇关于快速排序的论文!可能值得一读。