尝试用 ruby​​ 编写排序程序 - 堆栈级别太深（系统堆栈错误）

Question

我正在读 Chris Pine 的书“Learn to Progam”（这是关于 Ruby 的）。现在我正在尝试编写一个对单词进行排序的程序。不幸的是，我陷入了：第 16 行中的堆栈级别太深（系统堆栈错误），如果我在 Google 上正确搜索，则意味着存在无限循环，但我不知道为什么。

这是代码：

words = []
wordss = []
word = 'word'
i = 0
k = 0

def sortw array
  i = 0
  if    (array.length == 1) || (array.length == 0)
  else sort array, [], [], i
  end
  return array
end

def sort unsorted, unsort, sorted, i
  k = 0 # The error should be here, according to command prompt
  while i < unsorted.length

    while (unsorted[i] < unsorted[k])
      if    k < unsorted.length
        k = k + 1
      elsif k == unsorted.length
        sorted.push unsorted[i]
      else unsort.push unsorted[i]
      end
    end

    i = i + 1
    sort unsorted, unsort, sorted, i
  end

  if unsort.length != 1
    i = 0
    sort unsort, [], sorted, i
  else sorted.push unsort[0]
  end

  return sorted
end

puts 'type one word per line...'
puts 'typing enter on an empty line sorts the inputted words'

while word != ''
  word = gets.chomp
  words = words.push word
end

wordss = (sortw words)

puts 'your words'
puts words
puts 'sorted here'
puts wordss

Answer 1

您收到错误是因为递归由于排序算法的问题而没有停止。在 sort 方法中，k 始终小于 unsorted.length。这会导致其他数组、sorted 和 unsort 永远不会填充。

例如，尝试输入以下内容：

• dog
• zebra
• cat

另外，我认为您不想包含空行，因此我会将代码从：

words = Words.push word 更改为 words = Words .push word if word != ''

这将创建未排序数组：

• [0] dog
• [1] zebra
• [2] cat

下面编号的是递归排序的迭代方法。

#initial variable state:
i = 0
k = 1

1. 狗=狗
   • 跳过第二个 while 循环
   • i = 1
2. zebra >狗
   • 跳过第二个 while 循环
   • i = 2
3. cat <狗
   • 进入第二个while循环
     • k = 1，现在 cat <斑马，所以继续循环
     • k = 2，现在 cat = cat，因此退出
   • i = 3
4. 由于 i 现在等于未排序的数组长度，所以两个 while 循环永远不会不再进入。

因此，以下代码会导致无限循环，因为没有任何内容被推送到 unsort 数组中：

if unsort.length != 1
  i = 0
  sort unsort, [], sorted, i #Problem is that `unsort` and `sorted` are empty
elsif
...
end