学习插入在Ruby中排序

我刚刚通过在线发布的材料开始了麻省理工学院的算法入门课程。 除了课程，我还决定通过编写算法来学习/增强我的Ruby技能。

我在给出的第一个算法，即插入排序，我输入了以下代码，但是当我运行它时，我收到此错误：

insertionsort.rb：5：在`>’中：Fixnum与nil的比较失败（ArgumentError）

def insertionsort(num) for j in 2..num.length key = num[j] i = j - 1 while i > 0 and num[i] > key num[i+1] = num[i] i = i - 1 end num[i+1] = key end puts num end numbers = [23,34,46,87,12,1,66] insertionsort(numbers) 

我确信这是一个相当基本的问题，但我现在无法理解它是什么。 任何帮助或提示将非常感谢。

Answer 1

你正在超越数组的范围。 您给出的示例是假定1索引数组，但ruby中的数组是0索引的。 第一行应该是

 for j in 1...num.length 

Answer 2

另一个答案是正确的，您将超过数组中值的结尾，因为它是基于0的，但您需要进行其他更改才能使算法工作：

 for j in 1..(num.length - 1) 

和

 while i >= 0 and num[i] > key 

Answer 3

只是对另一个的一个小补充，优秀的答案：

我认为现在普遍认为0原点索引比1原点索引具有许多实际和经验上的优势。 经验表明它只是“更好地工作”并且不易出错。

这就是为什么许多程序员从零开始编号，以及令人惊讶的“普通”人。

Answer 4

虽然这个练习真的很酷，但根据这篇优秀的博客文章，你应该避免编写自己的排序并依赖内置的Array :: sort

http://philcrissman.com/2010/07/18/how-not-to-write-sorting-algorithms-in-ruby/

Answer 5

最简单的实现是这样的：

 def insertion_sort(arr) for i in (1...(arr.size)) if arr[i-1] > arr[i] i.downto(1) do |el| if arr[el] < arr[el-1] arr[el-1], arr[el] = arr[el], arr[el-1] end end end end arr end arr = [5, 2, 4, 6, 1, 3] p insertion(arr) 

注意：为了提高算法的效率，可以使用二进制搜索进行元素比较。

什么是插入排序？