algorithm - 生成“接近排序”或“k 排序”列表的算法？

Question

我想生成一些测试数据来测试将“k个排序”列表（每个元素距正确排序位置最多k个位置的列表）合并到一个完全排序的列表中的函数。我有一种可行的方法，但我不确定它的随机性有多好，我觉得应该有一种更简单/更优雅的方法来做到这一点。我目前的做法：

1. 生成与整数索引配对的 n 个随机元素。
2. 对随机元素进行排序。
3. 将每个元素的配对索引设置为其排序位置。
4. 向后遍历元素，将每个元素与列表中其后面 1 到 k 个位置之间的随机距离的元素交换。只有当它的配对索引是它的当前索引时才与目标元素交换（这避免了交换一个已经不合适的元素并将它移动到远离它应该在的位置的 k 个位置之外）。
5. 将扰动的元素复制到另一个列表中。

就像我说的那样，这可行，但我对替代/更好的方法感兴趣。

Answer 1

我认为你可以用随机整数填充一个数组，然后使用自定义停止条件对其运行快速排序。

如果在特定的快速排序递归中，您start和end索引之间的距离小于k，则只需返回而不是继续递归。

由于快速排序的工作原理，start..end区间中的每个数字都属于该区域的某个位置；最坏的情况是它array[start]可能真正属于array[end]（或反之亦然）以真正排序的顺序。因此，确保start和end不超过k分开就足够了。

Answer 2

您可以生成随机数数组，然后像在shellsort中一样对其进行 h 排序，但是当h小于k时，没有最后的排序步骤。

Answer 3

第 1 步：随机置换长度为 k 的不相交段。（例如 1 到 K，k+1 到 2k ...）

第 2 步：通过交换再次有条件地置换（它们不会破坏 k 排序假设 (1+t yo k+t, k+1+t to 1+2k+t ...) 其中 t 是介于 1 之间的数字和 k (最好是 k/2)

可能使用不同的 t 多次重复步骤 2。

Answer 4

如果我理解这个问题，你想要一个算法来随机选择一个长度的单一k排序列表，从所有长度排序列表n的宇宙中统一选择。（然后，您将运行此算法时间以生成列表作为输入测试数据。）Uknmm

第一步是计算它们。的大小是U多少？|U|

下一步是枚举它们。F在整数(1,2,...,|U|)和k长度的排序列表之间创建任何一对一映射n。

x然后随机选择一个介于 1 和 1 之间的整数|U|，然后申请F(x)得到列表。