小智 8
知道哪种排序算法的性能更好取决于您的数据和情况.
如果你在谈论一般/实际的术语,
Quicksort(你随机选择枢轴/只选择一个固定的,最坏情况下的Omega(n ^ 2))可能比红黑树更好,因为(不一定按重要性排序)
Quicksort就位.保持低内存.假设这个quicksort例程是处理大量数据的程序的一部分.如果您继续使用大量内存,您的操作系统可能会开始交换您的进程内存并丢弃您的性能.
Quicksort内存访问是本地化的.这适用于缓存/交换.
Quicksort可以很容易地并行化(这些天可能更相关).
如果您通过使用数组来尝试优化二叉树排序(使用二进制树而不平衡),您将最终执行类似Quicksort的操作!
红黑树有内存开销.您可能需要多次分配节点,使用树的内存需求是使用数组的两倍/三倍.
排序后,假设您想要第1045个(比较)元素,您需要在树中维护订单统计信息(因此会产生额外的内存成本),并且您将拥有O(logn)访问时间!
红黑树只有访问下一个元素的开销(指针查找)
红黑树与缓存不兼容,指针访问可能导致更多交换.
红黑树的旋转将增加O(nlogn)中的常数因子.
也许最重要的原因(但如果你有lib等可用,则无效),Quicksort非常易于理解和实现.即使是学校的孩子也能理解!
我会说你试着测量两种实现,看看会发生什么!
另外,Bob Sedgewick做了一个关于quicksort的论文!可能值得一读.