如何高效地*近似*排序一个列表？

Question

我有一个项目列表，我想对它们进行排序，但我希望有一个小的随机因素，使它们不是严格按顺序排列，只是平均有序。

最有效的方法是什么？

如果随机数质量不是特别好，例如它只是基于输入的随机排序，例如早期终止不完整排序，我不介意。

上下文中，通过引入一些不精确性来实现几乎贪婪的搜索；这是在紧密循环中完成的，因此需要考虑排序和调用random()的速度。

我的当前代码是对其执行std::sort（这是C++），然后只在数组的早期部分进行非常短的洗牌：

for(int i=0; i<3; i++) // I know I have more than 6 elements
    std::swap(order[i],order[i+rand()%3]);

- Will

---

将列表排序，然后移动一些元素？ - hugomg

不得不问：为什么？- 你不能使用现有的排序算法，然后通过提前退出来“打破”它吗？ - Randy

我会对列表进行排序，然后随机交换其中的元素，交换次数也是随机的。 - Sergey Kalinichenko

@aix 如果一个快速排序算法可以提前终止，那么它的速度会比同样的快速排序加上一步置换更快；但是如果你回答了，我们就可以更容易地进行比较，对吧？ - Will

@Will 我不认为我的建议值得成为真正的答案，因为它是最天真的方法，而且它的效率分析是微不足道的。 - Sergey Kalinichenko

Answer 1

使用 JSort 的前两个步骤。堆排序两次，但不执行插入排序。如果随机元素不够小，请重复此过程。

---

有一种方法（与不完整的JSort不同），可以更精细地控制结果的随机性，并且时间复杂度取决于随机性（需要更随机的结果，时间复杂度越小）。使用Soft heap的堆排序。关于软堆的详细描述，请参见pdf 1或pdf 2。

- Evgeny Kluev

Answer 2

假设你想要将数组按升序排序，我会采取以下步骤：

for M iterations
  pick a random index i
  pick a random index k
  if (i<k)!=(array[i]<array[k]) then swap(array[i],array[k])

M控制数组的“有序性”-随着M的增加，数组变得越来越有序。我认为M的合理值是n^2，其中n是数组的长度。如果选择随机元素太慢，则可以预先计算它们的索引。如果该方法仍然太慢，则可以牺牲排序质量来降低M的值。

- Dmitry Kamenetsky

Answer 3

你可以使用标准排序算法（是否有可用的标准库？），并传递一个谓词，该谓词“知道”给定两个元素中哪个小于另一个，或者它们是否相等（返回-1、0或1）。在谓词中引入一个罕见的（可配置的）情况，其中答案是随机的，通过使用随机数：

伪代码：

if random(1000) == 0 then
  return = random(2)-1   <-- -1,0,-1 randomly choosen

在这里，我们有1/1000的机会“混淆”两个元素，但这个数字严格取决于您要排序的容器的大小。

在1000种情况下，另一件需要添加的事情是删除“正确”的答案，因为那样不会混淆结果！

编辑：

if random(100 * container_size) == 0 then <-- here I consider the container size
{
   if element_1 < element_2
      return random(1); <-- do not return the "correct" value of -1
   else if element_1 > element_2
      return random(1)-1; <-- do not return the "correct" value of 1
   else
      return random(1)==0 ? -1  : 1; <-- do not return 0
}

在我的伪代码中： random(x) = y，其中 0 <= y <= x。

- vulkanino

---

根据算法的不同，编写搜索功能以抵抗比较器产生的不一致结果可能会非常棘手。您可能会轻易地超出您认为正在处理的区域的末尾，或者认为已经完成排序，而实际上几乎什么都没有做。显然，细节因语言而异，但例如在C或C++中，将不一致的比较器传递给qsort或std::sort是未定义的行为。 - Steve Jessop

@Steve 你说的undefined是指什么？是指你没有得到一个排序好的容器（这正是他想要的），而不是程序崩溃了！ - vulkanino

对于 C 和 C++，这是未定义行为，按照标准中定义的意义。是的，如果您给它一个不一致的比较器，实现允许崩溃，并且我见过发生这种情况。在其他语言（例如 Java）中，最糟糕的情况是会抛出异常。 - Steve Jessop

Answer 4

如果你确定元素距离它们应该在的位置最多有k个索引，你可以将快速排序的时间复杂度从N log(N)降低到N log(k)。

编辑：

更具体地说，你可以创建k个桶，每个桶包含N/k个元素。

你可以对每个桶进行快速排序，这需要k * log(k)的时间，然后对N/k个桶进行排序，这需要N/k log(N/k)的时间。将这两个相乘，你可以在N log(max(N/k,k))的时间内完成排序。

这种方法很有用，因为你可以并行运行每个桶的排序，从而减少总运行时间。

这种方法只适用于你确定列表中的任何元素在排序后最多与其正确位置相差k个索引的情况下。但我不认为你有任何限制。

- user482594

---

这不是我想要的，但我非常好奇你的意思是什么；能否请您提供更详细的解释或链接？ - Will

@Will：我认为他的意思是执行快速排序，但当你当前正在排序的块的大小达到 k 或更小时，就退出。 - Steve Jessop

Answer 5

一种可能需要更多空间但可以保证现有的排序算法不需要修改的方法是创建一个排序值的副本，然后在排序之前以某种方式修改这些值（然后使用修改后的值进行排序）。

例如，如果要排序的数据是一个简单的字符字段Name[N]，则添加一个字段（假设数据在结构体或类中）称为NameMod[N]。用Name的副本填充NameMod，但添加一些随机性。然后3%的时间（或适当的时间）更改名称的第一个字符（例如，将其更改为+/-一个或两个字符）。然后10%的时间更改第二个字符+/-几个字符。

然后通过您喜欢的任何排序算法运行它。好处是您可以轻松更改这些百分比和随机性。排序算法仍将正常工作（例如，它不会出现比较函数返回不一致结果的问题）。

- Mark Wilkins

Answer 6

将列表分成两个大小相等的部分。使用任何通常的算法单独对每个部分进行排序。然后合并这些部分。像平常一样执行一些合并迭代，比较合并的元素。对于其他合并迭代，不要比较元素，而是从同一部分选择元素，就像在上一步中一样。不必使用 RNG 来决定如何处理每个元素。仅忽略每 N 个元素的排序顺序。

该方法的另一个变体几乎可以在原地对数组进行排序。将数组拆分为具有奇/偶索引的两个部分。对它们进行排序。（甚至可以使用适当修改的迭代器的标准 C++ 算法，如 boost::permutation_iterator）。在数组末尾保留一些有限的空间。从末尾开始合并部分。如果合并部分将覆盖其中一个未合并的元素，请选择此元素。否则按排序顺序选择元素。随机性水平取决于保留空间的数量。

- Evgeny Kluev

Answer 7

冒泡排序来拯救！

对于一个未排序的数组，你可以选择几个随机元素并将它们向上或向下冒泡。（也许通过旋转会更有效率）很难控制（无）序的数量，即使你选择了所有N个元素，你也不能确定整个数组是否已排序，因为元素被移动，你无法确保只触摸了每个元素一次。

顺便说一句：这种问题往往出现在游戏引擎中，其中候选移动列表保持大致排序（因为加权采样），每次迭代后进行排序太昂贵，只有一个或几个元素预计会移动。

- wildplasser

Answer 8

取数据的一个小随机子集并对其进行排序。您可以使用此作为一个映射，提供每个元素应该在最终接近排序列表中出现的估计值。现在，您可以扫描整个列表并移动/交换不在良好位置的元素。

基本上这是O(n)，假设子集的小初始排序不需要太长时间。希望您可以构建地图，使得可以快速提取估计值。

- Aaron McDaid