为什么rindex和index会改变选择排序的输出？

Question

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

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])

在我看来，这应该无关紧要，因为索引就是一个索引，无论它是来自右侧还是左侧。使用rindex和index不是仅仅改变了流程(对于重复的条目)，但仍然输出有序列表吗？

我忽略了什么？

Answer 1

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

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索引。