0

我正在完成一些非常基本的算法练习，我对选择排序的这种实现感到困惑：

def selection_sort(xs)
  len = xs.length
  len.times do |i|
    low = xs[i...len].min
    tmp = xs[i]
    xs[i] = low    
    xs[xs.rindex(low)] = tmp
  end
  xs
end

代码工作正常，但是，如果我使用xs[xs.index(low)] = tmp而不是xs[xs.rindex(low)] = tmp，该函数在以下测试中无法正常工作：

selection_sort([3, 6, 2, 7, 4, 1, 4, 5, 6, 7, 8, 0])
selection_sort([0, 8, 7, 6, 5, 4, 1, 4, 7, 2, 6, 3])

在我看来，这无关紧要，因为索引是来自右侧还是左侧的索引。不会使用rindexvsindex只是更改流程（对于重复条目），但仍会输出有序列表？

我在看什么？

4

1 回答 1

2

发生的情况是您在重新分配低值之后测试索引，但不是在您重新分配处于低值新位置的值之前。所以，让我们考虑一下：

xs = [4,3,2,1]
i = 2
low = [2, 1].min = 1
tmp = xs[i] = 2

现在，您分配xs[i] = low，这意味着您的数组现在看起来像[4,3,1,1]。此时，xs.index(1)将返回2，因为您只是将低值放在该位置！使用rindex得到你3，因为它会找到用作低值的值，而不是你刚刚替换的值。

您可以index通过在进行第一次替换之前获取索引来对没有重复值的列表进行调用：

def selection_sort(xs)
  len = xs.length
  len.times do |i|
    low = xs[i...len].min
    tmp = xs[i]
    tmpindex = xs.index(low)
    xs[i] = low
    xs[tmpindex] = tmp
  end
  xs
end

但是，由于您正在测试的列表确实具有重复值，因此您需要使用 rindex 来获得正确的偏移量，否则您可以获得超出i...len范围范围的索引。

如果你想index在可以包含多个值的列表上使用，你必须确保你只会在你当前正在操作的切片中找到低值，然后将它偏移切片开始位置：

def selection_sort(xs)
  xs.length.times do |i|
    slice = xs[i..-1]
    low, tmp = slice.min, xs[i]
    xs[i], xs[i + slice.index(low)] = low, tmp
  end
  xs
end

此外，通过从而slice不是从获取索引xs，我们不必担心会xs导致我们得到不正确索引的变化low。

于 2013-07-17T22:48:53.280 回答