随机化随机数组快速排序

Question

我是计算机科学专业的第一年，我了解到可以通过在开始排序之前随机化数组来避免 QuickSort 的最坏情况。

但这是否也适用于输入已经是随机的情况？我认为随机排列数组的机会比洗牌更多吗？

Answer 1

随机化以避免 O(something) 纯粹是学术上的细微差别。 Math.random()太费时了，效果会不好

真正重要的是

• 执行的操作总数
• 避免随机访问内存以避免缓存未命中（google 关于缓存命中率的一些事情）。

在这方面，好的排序算法是

• Yarroslavkij 的双枢轴快速排序，这是 java 排序中的默认设置。这个通过选择两个枢轴并将数组分成 3 个部分，以一种更好的确定性方式解决了最坏的情况。
• 基数排序、桶排序或派生，在我看来可能是最快的算法，但是使用 2n 内存。