1

这是 C++ 中的插入排序算法（来自教程）：

void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}

这就是我在 Ruby 中所做的

a = [12, 1, 18, -3, -2, 66, 31]
puts a

def insertion_sort(source)
    source.to_enum.with_index(1).each do |item, i|
        j = i
        while((j>0) && (source[j-1] > source[j]))
            source[j], source[j-1] = source[j-1], source[j]
            j -= 1  
        end
    end
end

insertion_sort(a)
puts a

它抛出一个错误comparison of Fixnum with nil failed (ArgumentError)。可能是因为溢出。

我做错了什么？

4

2 回答 2

2

在C++您拥有的版本中(i = 1; i < length; i++)。这意味着，它不会运行最后一轮 where i = length。那将超出数组范围。

在ruby中，因为您将索引的偏移量设置为1，所以最后一轮，您将拥有i = length。故source[length]出source，故归nil。

1 > nil  # source[j-1] > source[j] when j = length
# ArgumentError: comparison of Fixnum with nil failed
于 2012-10-29T04:46:48.713 回答
1

虽然@oldergod 已经回答了你的问题，但我只想为这个问题添加一些修复。

这里是从算法 gem中获取的代码示例

def insertion_sort(container)
  return container if container.size < 2
  (1..container.size-1).each do |i|
    value = container[i]
    j = i-1
    while j >= 0 and container[j] > value do
      container[j+1] = container[j]
      j = j-1
    end
    container[j+1] = value
  end
  container
end

在这里，您遍历一个数字 ，1容器的第二个索引，到container.size - 1最后一个索引。

于 2012-10-29T07:54:30.820 回答