建议我们在快速排序之前将数组洗牌.
但是,如果我们想要快速排序列表,则首先应该使用O(nlogn)随机播放列表,例如,我们为列表中的每个项目分配一个随机密钥,然后合并(key,item)列表.
然后我的问题是:
如果我们必须先花费O(nlogn)洗牌清单,那么在OCaml中实现快速排序列表的重点是什么？
我们应该直接使用mergesort,对吧？
在OP的问题中:
但是,如果我们想要快速排序列表,则首先将洗牌列表取O(nlogn)
我认为随机改组只O(n)花费时间,如果你先将列表转换为数组,然后使用Fisher-Yates shuffle,这也是Python的random.shuffle中使用的算法.