使用 Python 自下而上的 MergeSort

Question

我花了无数个小时来尝试做到这一点。谁能指出我的错误？

a 只是一个列表，tmp 是一个大小为 len(a)

的空列表

z 基本上是 len(a)

a = [6,5,4,3,2,1] print 'unsorted:',a z = len(a) tmp = range(len(a))

这是我的排序函数：

def sort(a,tmp):
        width=1
        while(width<z):
                p=0
                while(p<z):
                        left =p
                        middle = p+width
                        right = p+2*width
                        merge(a,left,middle,right,tmp)
                        p = p+2*width
                t=0        
                while(t<z):
                    a[t]=tmp[t]
                    t=t+1
                width=width*2
                print '\n'

这里是合并函数：

def merge(a,iLeft,iMiddle,iRight,tmp):
        i = iLeft
        j = iMiddle
        k = iLeft
        print iLeft,iMiddle,iRight,'[',i,j,k,']'
        #print i ,j, k,'\n\n'

        while(i<iMiddle or j<iRight):
                if(i<iMiddle and j<iRight):
                        if(a[i]<a[j]):
                                tmp[k]=a[i]
                                i += 1
                                k += 1
                        else:
                                tmp[k]=a[j]
                                j += 1
                                k += 1

                elif (i==iMiddle):
                        tmp[k] = a[j]
                        j += 1
                        k += 1
                elif (j==iRight):
                        tmp[k]= a[i]
                        i += 1
                        k += 1

[此可视化] 可能会有所帮助。我仍然不知道为什么它会这样。

我不确定我哪里出错了？是缩进还是循环？

Output ::
unsorted: [6, 5, 4, 3, 2, 1]
0 1 2 [ 0 1 0 ]
2 3 4 [ 2 3 2 ]
4 5 6 [ 4 5 4 ]


0 2 4 [ 0 2 0 ]
4 6 8 [ 4 6 4 ]
Traceback (most recent call last):
  File "BUmer.py", line 45, in <module>
    sort(a,tmp)
  File "BUmer.py", line 14, in sort
    merge(a,left,middle,right,tmp)
  File "BUmer.py", line 27, in merge
    if(a[i]<a[j]):
IndexError: list index out of range

This visualization 可能会有帮助。我仍然不知道为什么会这样。

Answer 1

尽管这是一项勇敢的努力，但您犯的 主要错误 是嵌套的流量控制方法——人类的思维只能处理这么多的嵌套 while-循环。此外，合并函数修改 a 到位的事实使得确定正在发生的事情变得极其困难。即使您有惊人的头脑可以跟踪所有这些动作，也请将大脑能量用于解决问题而不是流量控制！

一般来说，您想尽最大努力使您的程序保持平坦平坦 -- 避免嵌套流程控制。此外，除非您正在进行专门的面向对象编程，否则您应该尝试 return 一个特定的值，而不是就地修改 a。

这是另一种合并排序方法，它试图使事情变得更加平坦和明确：

def merge(merged, a, b):

    if a and b:
        return merge(merged + [min(a[0], b[0])],
                     a[1:] if min(a[0], b[0]) == a[0] else a,
                     b[1:] if min(a[0], b[0]) == b[0] and not a[0] == b[0] else b
                     )

    elif a and not b and len(a) > 1:
        return merged + merge([], a[:len(a)/2], a[len(a)/2:])
    elif a and not b:
        return merged + a
    elif b and not a  and len(b) > 1:
        return merged + merge([], b[:len(b)/2], b[len(b)/2:])
    elif b and not a:
        return merged + b
    else:
        return merged

def mergesort(lst):

    if not lst:
        return []
    elif len(lst) == 2:
        return [min(lst), max(lst)]
    elif len(lst) == 1:
        return lst
    else:
        return merge([], mergesort(lst[:len(lst)/2]), mergesort(lst[len(lst)/2:]))

这种保持明确和最小化流程控制结构的努力在称为 函数式编程 的编程风格中很常见。您可以在此处访问一本很棒的免费书籍：

http://www.oreilly.com/programming/free/files/functional-programming-python.pdf

意识到这可能不是您正在寻找的确切答案，但我希望它能有所帮助。

Answer 2

我觉得很累，但很开心。我通过 PythonTutor 上惊人的可视化工具偶然发现了答案，并且非常关注迭代的数学。

该程序适用于长度为 2 的幂的数组。其他一切都给出了一个超出索引的数组异常。我应该实现一个 try-except 块来处理这些事情。

不管怎样，现在我知道了。感谢 snakes_on_a_keyboard 对函数式编程的指导。

我之所以不透露这个问题的更多细节，是因为 snakes_on_a_keyboard 已经提供了一个更好更优雅的解决方案。

使用 Python 自下而上的 MergeSort

Bottom Up MergeSort using Python

python

mergesort

bottom-up