生成“几乎排序”或“ k排序”列表的算法？

问题描述

我想生成一些测试数据来测试将 k个排序列表（每个元素距离其正确排序位置最多k个位置的列表）合并到一个完全排序的列表中的功能。我有一种可行的方法，但是我不确定它的随机化程度如何，我觉得应该有一个更简单/更优雅的方法来做到这一点。我当前的方法：

1. 生成n个与整数索引配对的随机元素。


2. 对随机元素进行排序


3. 将每个元素的配对索引设置为其排序位置。


4. 向后遍历元素，将每个元素与元素交换之间的随机距离1和k在列表中的后面。仅当目标元素的配对索引为当前索引时，才与目标元素交换（这避免了交换已经不适当的元素并将其移动到比其应有的位置多k个位置的位置）。


5. 将受干扰的元素复制到另一个列表中。

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

解决方案

您可以生成随机数数组，然后像，但是当 h 小于 k 时，没有最后的排序步骤。 / p>

I want to generate some test data to test a function that merges 'k sorted' lists (lists where each element is at most k positions away from it's correct sorted position) into a single fully sorted list. I have an approach that works but I'm not sure how well randomized it is and I feel there should be a simpler / more elegant way to do this. My current approach:

1. Generate n random elements paired with an integer index.
2. Sort random elements.
3. Set paired index for each element to its sorted position.
4. Work backwards through the elements, swapping each element with an element a random distance between 1 and k positions behind it in the list. Only swap with the target element if its paired index is its current index (this avoids swapping an element that is already out of place and moving it further than k positions away from where it should be).
5. Copy the perturbed elements out into another list.

Like I say, this works but I'm interested in alternative / better approaches.

解决方案

You can generate array of random numbers and then h-sort it like in shellsort, but without fiew last sorting steps when h is less then k.

这篇关于生成“几乎排序”或“ k排序”列表的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！