如何编写合并排序？

我正在尝试实现合并排序，并且在运行代码时出现stack level too deep (SystemStackError)错误。 我不确定这个问题是什么。

 def merge_sort(lists) lists if lists.count == 1 middle = lists[0..(lists.count / 2) - 1 ] left = lists[0..middle.count - 1] right = lists[middle.count..lists.count] x = merge_sort(left) y = merge_sort(right) end merge_sort [1,2,3,4,5,6,7,8] 

任何帮助都会很棒！

Answer 1

写这个

  return lists if lists.count == 1 

代替

  lists if lists.count == 1 

在Ruby中，默认情况下始终返回方法last语句。 但是如果你想有条件地从除最后一行之外的任何行的中间返回，你必须明确地使用return关键字。

Answer 2

来自维基百科 ：

 def mergesort(list) return list if list.size <= 1 mid = list.size / 2 left = list[0...mid] right = list[mid...list.size] merge(mergesort(left), mergesort(right)) end def merge(left, right) sorted = [] until left.empty? || right.empty? if left.first <= right.first sorted << left.shift else sorted << right.shift end end sorted.concat(left).concat(right) end 

Answer 3

带注释的简化版

 def merge_sort(arr) # 0. Base case return arr if arr.length <= 1 # 1. Divide mid = arr.length / 2 arr0 = merge_sort(arr[0, mid]) arr1 = merge_sort(arr[mid, arr.length]) # 2. Conquer output = merge(arr0, arr1) end def merge(l, r) output = [] until l.empty? || r.empty? output << if l.first <= r.first l.shift else r.shift end end # The order of `concat(l)` or `concat(r)` does not matters output.concat(l).concat(r) end 

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms

Answer 4

这是一个很好的方法。 起初有点棘手，但要坚持下去。

 def merge_sort list if list.length <= 1 list else mid = (list.length / 2).floor left = merge_sort(list[0..mid - 1]) right = merge_sort(list[mid..list.length]) merge(left, right) end end def merge(left, right) if left.empty? right elsif right.empty? left elsif left.first < right.first [left.first] + merge(left[1..left.length], right) else [right.first] + merge(left, right[1..right.length]) end end 

Answer 5

试试这个：

 def merge_arrays(left, right) sorted_array = [] until left.empty? || right.empty? sorted_array << (left.first < right.first ? left.shift : right.shift) end sorted_array + left + right end def merge_sort(array) return array if array.size <= 1 left = merge_sort array[0...(array.size / 2)] right = merge_sort array[(array.size / 2)...array.size] merge_arrays left, right end puts merge_sort Array.new(10) { rand(0...100) }