使用红黑树进行排序
在a上插入的最坏情况运行时间red-black tree是O(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
