使用递归的归并排序算法
Merge sort algorithm using recursion
我在做奥丁计划。练习题是:使用递归创建归并排序算法。以下是根据某人的解决方案修改的:
def merge_sort(arry)
# kick out the odds or kick out of the recursive splitting?
# I wasn't able to get the recombination to work within the same method.
return arry if arry.length == 1
arry1 = merge_sort(arry[0...arry.length/2])
arry2 = merge_sort(arry[arry.length/2..-1])
f_arry = []
index1 = 0 # placekeeper for iterating through arry1
index2 = 0 # placekeeper for iterating through arry2
# stops when f_arry is as long as combined subarrays
while f_arry.length < (arry1.length + arry2.length)
if index1 == arry1.length
# pushes remainder of arry2 to f_arry
# not sure why it needs to be flatten(ed)!
(f_arry << arry2[index2..-1]).flatten!
elsif index2 == arry2.length
(f_arry << arry1[index1..-1]).flatten!
elsif arry1[index1] <= arry2[index2]
f_arry << arry1[index1]
index1 += 1
else
f_arry << arry2 [index2]
index2 += 1
end
end
return f_arry
end
第一行return arry if arry.length == 1
是否将其踢出数组的递归拆分,然后绕过方法的递归拆分部分回到重组部分?似乎它应该在它递归通过时返回到该部分后继续重新拆分它。
为什么一定要 flatten
-ed?
理解第一行的最简单方法是理解 merge_sort
绑定的唯一契约是 "return a sorted array" - 如果数组只有一个元素 (arry.length == 1
) 它 已经排序 - 所以不需要做任何事情!只需 return 数组本身。
在递归中,这称为 "Stop condition"。如果您不提供停止条件 - 递归将永远不会结束(因为它总是会调用自己 - 而且永远不会 return)!
你需要 flatten
结果的结果,是因为你将数组作为元素推送到结果数组中:
arr = [1]
arr << [2, 3]
# => [1, [2, 3]]
如果您尝试仅在迭代结束时展平生成的数组,而不是在添加元素时展平,则会出现问题,因为它的 length会偏斜:
arr = [1, [2, 3]]
arr.length
# => 2
虽然 arr
包含三个 数字 它只有 两个元素 - 这会破坏你的解决方案。
您希望数组中的所有元素都是数字,而不是数组。 flatten!
确保数组中的所有元素都是原子,如果不是,它会将子数组的元素添加到自身而不是子数组:
arr.flatten!
# => [1, 2, 3]
您可能要考虑的另一个选项(并且会更有效)是使用 concat
代替:
arr = [1]
arr.concat([2, 3])
# => [1, 2, 3]
此方法将作为参数传递的数组中的所有元素添加到调用它的数组中。
我在做奥丁计划。练习题是:使用递归创建归并排序算法。以下是根据某人的解决方案修改的:
def merge_sort(arry)
# kick out the odds or kick out of the recursive splitting?
# I wasn't able to get the recombination to work within the same method.
return arry if arry.length == 1
arry1 = merge_sort(arry[0...arry.length/2])
arry2 = merge_sort(arry[arry.length/2..-1])
f_arry = []
index1 = 0 # placekeeper for iterating through arry1
index2 = 0 # placekeeper for iterating through arry2
# stops when f_arry is as long as combined subarrays
while f_arry.length < (arry1.length + arry2.length)
if index1 == arry1.length
# pushes remainder of arry2 to f_arry
# not sure why it needs to be flatten(ed)!
(f_arry << arry2[index2..-1]).flatten!
elsif index2 == arry2.length
(f_arry << arry1[index1..-1]).flatten!
elsif arry1[index1] <= arry2[index2]
f_arry << arry1[index1]
index1 += 1
else
f_arry << arry2 [index2]
index2 += 1
end
end
return f_arry
end
第一行
return arry if arry.length == 1
是否将其踢出数组的递归拆分,然后绕过方法的递归拆分部分回到重组部分?似乎它应该在它递归通过时返回到该部分后继续重新拆分它。为什么一定要
flatten
-ed?
理解第一行的最简单方法是理解 merge_sort
绑定的唯一契约是 "return a sorted array" - 如果数组只有一个元素 (arry.length == 1
) 它 已经排序 - 所以不需要做任何事情!只需 return 数组本身。
在递归中,这称为 "Stop condition"。如果您不提供停止条件 - 递归将永远不会结束(因为它总是会调用自己 - 而且永远不会 return)!
你需要 flatten
结果的结果,是因为你将数组作为元素推送到结果数组中:
arr = [1]
arr << [2, 3]
# => [1, [2, 3]]
如果您尝试仅在迭代结束时展平生成的数组,而不是在添加元素时展平,则会出现问题,因为它的 length会偏斜:
arr = [1, [2, 3]]
arr.length
# => 2
虽然 arr
包含三个 数字 它只有 两个元素 - 这会破坏你的解决方案。
您希望数组中的所有元素都是数字,而不是数组。 flatten!
确保数组中的所有元素都是原子,如果不是,它会将子数组的元素添加到自身而不是子数组:
arr.flatten!
# => [1, 2, 3]
您可能要考虑的另一个选项(并且会更有效)是使用 concat
代替:
arr = [1]
arr.concat([2, 3])
# => [1, 2, 3]
此方法将作为参数传递的数组中的所有元素添加到调用它的数组中。