我一直在阅读一本关于排序算法的基础书籍。为了解决这个问题,我尝试编写一个简单的程序来实现该算法。
编辑:我省略了以前版本中的重要行 - 请参阅下面的评论。
这是我的选择排序:
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
我喜欢以一种递归的方式来做这件事,存储的状态更少,并且没有嵌套循环。有什么建议吗?
最佳答案
尝试在 index = i
之后立即添加 smallest = e
,这样您就可以对目前找到的最小值进行统计。
我还要注意,选择排序通常是就地实现的,即,扫描列表的第 1-N 个位置以查找最小值,然后将其与第一个元素交换,然后对第 2-N 个元素重复该过程, 3-N 等。不需要第二个数组或从数组中间删除元素的费用。
关于ruby - 这是选择排序算法的忠实再现吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21515940/