2

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

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

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

4

2 回答 2

1

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

通常，您希望尽最大努力保持程序平坦——避免嵌套流控制。此外，除非您正在执行专门的面向对象编程，否则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

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

于 2016-05-22T01:24:08.823 回答
1

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

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

无论如何，现在我知道了。感谢snakes_on_a_keyboard 对函数式编程的指导。

我没有透露更多细节的原因是因为snakes_on_a_keyboard 已经提供了一个更好、更优雅的解决方案。

于 2016-05-22T08:46:56.443 回答