ocaml - 我应该在 OCaml 中快速排序之前对列表进行洗牌吗？

Question

建议我们在快速排序之前对数组进行洗牌。

但是，如果我们要对列表进行快速排序，则首先对列表进行洗牌O(nlogn)，例如，我们为列表中的每个项目分配一个随机键，然后对 (key, item) 列表进行合并排序。

那么我的问题是：

如果我们必须先花O(nlogn)时间洗牌，那么在 OCaml 中为列表实现快速排序有什么意义呢？

我们应该直接使用归并排序，对吧？

Answer 1

在OP的问题中：

但是，如果我们想快速排序一个列表，首先洗牌列表将花费 O(nlogn)

我认为，O(n)如果您首先将列表转换为数组，然后使用Fisher–Yates shuffle（这也是 Python 的 random.shuffle 中使用的算法），随机洗牌只会花费时间。

Answer 2

我会按照你的建议使用合并排序。合并排序甚至比快速排序更适合函数式语言。