ruby - 这是选择排序算法的忠实再现吗？

Question

我一直在阅读一本关于排序算法的基础书籍。为了解决这个问题，我尝试编写一个简单的程序来实现该算法。

编辑:我省略了以前版本中的重要行 - 请参阅下面的评论。

这是我的选择排序:

class SelectionSorter

  attr_reader :sorted

  def initialize(list)
    @unsorted = list
    @sorted = []
  end

  def select(list)
    smallest = list.first
    index = 0
    list.each_with_index do |e,i|
      if e < smallest
        smallest = e
        index = i
      end
    end
    @sorted << list.delete_at(index)
  end

  def sort
    @unsorted.length.times { self.select(@unsorted) }
  end

end

这是一个测试:

require 'minitest/autorun'
require_relative 'sort'

class SelectionSortTest < MiniTest::Test

  describe SelectionSorter do

    it 'sorts a randomly generated list' do
      list = (1..20).map { rand(100-1) + 1 }
      sorted_list = list.sort
      sorter = SelectionSorter.new(list)
      sorter.sort
      sorter.sorted.must_equal sorted_list 
    end

  end

end

我喜欢发表评论，尤其是关于这是否真的是算法的忠实实现。

编辑 2:

好的 - 这是我的就地代码。这是我想避免的事情，因为它感觉过程很讨厌，带有嵌套循环。但是，我认为这是一个忠实的实现。

class SelectionSorter

  def sort(list)
    sorted_boundary = (0..(list.length)-1)
    sorted_boundary.each do |sorted_index|
      smallest_index = sorted_index
      smallest_value = list[smallest_index]
      comparison = sorted_index + 1
      (comparison..(list.length-1)).each do |next_index|
        if list[next_index] < smallest_value
          smallest_index = next_index
          smallest_value = list[smallest_index]
        end
      end
      unless sorted_index == smallest_index
        list[smallest_index] = list[sorted_index]
        list[sorted_index] = smallest_value
      end
    end
    list
  end

end

我喜欢以一种递归的方式来做这件事，存储的状态更少，并且没有嵌套循环。有什么建议吗？

Answer 1

尝试在 index = i 之后立即添加 smallest = e，这样您就可以对目前找到的最小值进行统计。

我还要注意，选择排序通常是就地实现的，即，扫描列表的第 1-N 个位置以查找最小值，然后将其与第一个元素交换，然后对第 2-N 个元素重复该过程， 3-N 等。不需要第二个数组或从数组中间删除元素的费用。