快速排序非递归

Question

声明说：

编写一个非递归（负）函数，该函数给定整数列表（可能是无序的）函数将带有负数的相同列表返回正头和后退（无论它们之间的顺序如何）。该算法可以通过在快速排序中请求类似策略（尽管更简单）分区的形式来解决。

我把这个代码：

def negatius(a):
    fin = len(a) - 1
    i = 0
    b = [i]
    for i in range(len(a)):
        if a[i] < 0:
            b[fin] = a[i]
            i += 1
        else:
            b[fin] = a[i]
            fin += 1
    print "La llista és",b[fin]

a=[1,-2,3,-4,-3,5,6]
negatius(a)

并出现一个错误：局部变量"i"在赋值前引用。我不明白这个

Answer 1

您正在从最高索引 on 递增fin，并使用它来访问具有此索引的列表中的元素。 这不可能是正确的，因为这些索引不存在。

b[fin] = a[i]

和

b[fin] = a[i]
fin += 1

和

print "La llista és",b[fin]

同样在 if 中，否则您将附加到列表中。这也说不通。您应该附加一次并在另一种情况下作为前缀

def negatius(a):
    fin = len(a) - 1
    i = 0
    b = [i]
    for i in range(fin):
            if a[i] < 0:
                    b = [a[i]] + b  # prepend a to b
            else:
                    b += [a[i]]     # append a to b
    print "La llista és",b
a=[1,-2,3,-4,-3,5,6]
negatius(a)

指纹

La llista és [-3, -4, -2, 0, 1, 3, 5]

请注意，您正在将 0 添加到列表中，我怀疑这是否可以。