是否有一种非递归方法将每个列表元素分离到自己的列表中？
我正在查看维基百科关于合并排序的伪代码（以及其他网页，如 sortvis.org 和 sorting-algorithm.com），并看到合并的准备使用递归。
我很好奇是否有非递归的方法来做到这一点。
也许类似于列表中每个 i 元素的 ，i=[i-th element]。
我的印象是递归是将其保持在最小值，因为它是不可取的，因此我想到了这个问题。
以下是来自维基百科的合并排序递归部分的伪代码示例：
function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
I was looking at Wikipedia's pseudo-code (and other webpages like sortvis.org and sorting-algorithm.com) on merge sort and saw the preparation of a merge uses recursion.
I was curious to see if there is a non-recursive way to do it.
Perhaps something like a for each i element in list, i=[i-th element].
I am under the impression that recursion is keep-it-to-a-minimum-because-it's-undesirable, and so therefore I thought of this question.
The following is a pseudo-code sample of the recursive part of the merge-sort from Wikipedia:
function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
自下而上归并排序是归并排序的非递归变体。
另请参阅此维基百科页面以获取更详细的伪代码实现。
Bottom-up merge sort is a non-recursive variant of merge sort.
See also this wikipedia page for a more detailed pseudocode implementation.
列表切片效果很好。
List slicing works fine.
顺便说一句 - 递归本身并不是不可取的。
如果您的堆栈空间有限（您害怕堆栈溢出吗？;-)），或者在某些情况下函数调用的时间开销非常令人担忧，那么递归是不可取的。
在大多数情况下，这些条件并不成立；代码的可读性和可维护性将更加相关。在我看来，像合并排序这样的算法在递归表达时更有意义。
As an aside - recursion is not undesirable per se.
Recursion is undesirable if you have limited stack space (are you afraid of stackoverflow? ;-) ), or in some cases where the time overhead of function calls is of great concern.
For much of the time these conditions do not hold; readability and maintainability of your code will be more relevant. Algorithms like merge sort make more sense when expressed recursively in my opinion.