ruby - 创建一个几乎排序的数组

Question

我想尽可能高效地创建一个“几乎排序”的数组(为了探索列表中随机细微变化的影响，我希望经常调用这个例程)。

我有 Ruby 代码可以做我想做的事:

sortme = [ 'X','A','B','W','S','J','7','9','Q','E' ]
n = sortme.length

correctly_sorted = sortme.sort
# ["7", "9", "A", "B", "E", "J", "Q", "S", "W", "X"]

# Specific to this case, I'd like the disorder to be strongest at the
# start of the array. In general, I would like to be able to control
# it, in relation to the sorted positions.
sort_adjust = Array.new( n ) { |i| i + ( rand() * 50 ) / (i+10) }

adjust_indexes = (0...n).sort_by { |i| sort_adjust[i] }
# e.g. [0, 2, 1, 3, 4, 5, 6, 7, 9, 8]

almost_sorted = adjust_indexes.map { |i| correctly_sorted[i] }

# Example output
# ["7", "A", "9", "B", "E", "J", "Q", "S", "X", "W"]

我的解决方案执行两个 sort，一个 map，并调用 rand() N 次来填充一个临时数组。有什么方法可以减少对 Array 的方法调用次数，并提高效率吗？或者减少我调用 rand() 的次数，但仍然可以控制项目的洗牌？

Answer 1

如何应用标准和高效array shuffling algorithm , 但添加随机化？

基本算法为每个位置 i 选择一个随机位置 n>=j>=i 来交换值。相反，决定以概率 p 进行交换。对于 p=1，您有标准的改组算法(其中所有排列出现的可能性相同)，对于 p=0，数组将保持排序。