1

我是 Tcl 新手，为了学习，我正在尝试实现来自维基百科的合并排序算法伪代码：

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 before 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)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)

在我的 Tcl 脚本中，我这样做：

proc merge_sort { lst } {

   if { [llength $lst] <= 1 } {
       return $lst
   }

   set middle [expr {[llength $lst] / 2}]

   set left [lrange $lst 0 $middle]
   set right [lrange $lst [expr {$middle + 1}] [llength $lst]]

   set left [merge_sort $left]
   set right [merge_sort $right]

   return [merge $left $right]
}

根据我的调试尝试，在递归调用merge_sortproc 之前一切正常。

输出说我“堆栈空间不足（无限循环？） ”。老实说，我没有在代码中看到问题。我哪里错了？

4

1 回答 1

1

一个问题是您的代码用于[lrange $lst 0 $middle]获取字符串的左侧部分，但由于lrange' 的范围是从零开始的，这意味着对于两个成员的列表{7 8}，您将得到middle等于1和left将是{7 8}。

此外，由于您使用[lrange $lst [expr {$middle + 1}] [llength $lst]]for right，而不是对于同一个列表，它会导致一个空列表，因为[lrange $lst 2 2]对于两个成员列表是空的。

我还更改了用作最后一个索引的权利，因为这是一种常见的最佳实践，而不是lrange等效的。end[expr {[llength $lst] - 1}]

proc merge_sort { lst } {

   if { [llength $lst] <= 1 } {
       return $lst
   }

   set middle [expr {[llength $lst] / 2}]

   #for each x in m *before* middle add x to left
   set left [lrange $lst 0 [expr {$middle - 1}]]

   #for each x in m *after or equal* middle add x to right
   set right [lrange $lst $middle end]

   set left [merge_sort $left]
   set right [merge_sort $right]

   return [merge $left $right]
}
于 2012-12-02T08:27:48.730 回答