随机快速排序

Question

在随机快速排序中，我应该先将输入数据随机化，然后使用第一个元素作为枢轴，还是不应该改变输入数据，而是选择一个随机枢轴？

我有点不明白什么是需要随机分配的。

Answer 1

如果您的数组还没有随机分布，那么只需在数组上选择一个随机支点，这就是随机快速排序的目的。

如果数组以前是随机的，则使用普通的快速排序。

Answer 2

一个简单的方法是：

只需将数组输入保持原样。每次在数组中选择一个随机索引，并用最后一个元素替换它。然后，将最后一个元素作为枢轴，就像通常的快速排序一样。

希望能帮上忙。