使用红黑树进行排序

在a上插入的最坏情况运行时间red-black treeO(lg n),如果我in-order

walk在树上执行,则实际上访问了每个节点,因此打印排序后的集合的总最坏情况运行时间为O(n lg n)

我很好奇,为什么red-black trees不偏向于排序quick sort(平均情况下运行时间为)O(n lg n)

我看到这也许是因为red-black trees没有进行就地排序,但是我不确定,所以也许有人可以提供帮助。

回答:

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

如果您是在一般/实用方面讲,

Quicksort(一种随机选择枢轴的选择/仅选择一种固定的分类,使最坏的情况为Omega(n ^ 2))可能比Red-Black

Trees好,因为(不一定按重要性顺序排列)

  • Quicksort就位。保持您的内存占用量低。说这个快速排序例程是处理大量数据的程序的一部分。如果您继续使用大量内存,则操作系统可能会开始交换进程内存并浪费性能。

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

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

  • 如果您尝试通过使用数组来优化和优化二叉树排序(使用二叉树而不进行平衡),则最终会做类似Quicksort的事情!

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

  • 排序后,说出您想要第1045个(例如)元素,您将需要在树中维护订单统计信息(因此会增加存储成本),并且您将拥有O(logn)访问时间!

  • 红黑树的开销仅用于访问下一个元素(指针查找)

  • 红黑树不能很好地与缓存配合使用,并且指针访问可能会导致更多交换。

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

  • 也许是最重要的原因(但如果有lib等可用,则无效),Quicksort非常易于理解和实现。即使是小学生也能理解!

我会说您尝试衡量这两种实现,然后看看会发生什么!

另外,鲍勃·塞奇威克(Bob Sedgewick)撰写了关于快速排序的论文!可能值得一读。

以上是 使用红黑树进行排序 的全部内容, 来源链接: utcz.com/qa/427202.html

回到顶部