1

我试图使用 Hoare 分区方案编写快速排序算法。我很确定我的分区功能是正确的。我使用变量“交换”来指示左枢轴向右移动和右枢轴向左移动。Sort 函数适用于其他 Partition 算法，所以我认为这也很好。然而我得到了错误。

inp=[2,3,6,3,9,7,8,0,5]

#Swap Function
def Swap(List, i, j):
    temp=List[i]
    List[i]=List[j]
    List[j]=temp


#QuickSort Function
def QSort(List, Start, End):
    if Start < End:

        PIEnd=Partition(List, Start, End)

        QSort(List,Start,PIEnd)
        QSort(List,PIEnd+1,End)

    return List



#Partition Function
def Partition (List, Start, End):
    Swaps=0
    PIStart=Start #PI = Pivot Index
    PIEnd=End 

    for i in range(Start, End):
        if List[PIStart] > List[PIEnd]:
            Swap(List, PIStart, PIEnd)
            Swaps=Swaps+1       
        if Swaps % 2 ==0:
            PIStart=PIStart+1
        else:
            PIEnd=PIEnd-1

    return PIEnd

print(QSort(inp, 0, 8))
4

1 回答 1

1

看看这两个地方...

# QSort ...
        PIEnd=Partition(List, Start, End)

        QSort(List,Start,PIEnd)
        QSort(List,PIEnd+1,End)

# Partition
        if Swaps % 2 ==0:
            PIStart=PIStart+1
        else:
            PIEnd=PIEnd-1

如果您在任何分区中有均匀数量的交换，则PIEnd不会更改，并且您在 QSort 中的间接递归将坚持相同的参数。您的第一个低半递归执行此操作。重新审视你的逻辑。对于初学者，您不应该依赖全局变量来解决问题。

这是我为递归跟踪检测代码的方法：

call_count = 0
indent = ""


#QuickSort Function
def QSort(List, Start, End):
    global call_count, indent
    indent += "  "
    call_count += 1
    print(indent, "ENTER QSort", Start, End, List)

    if call_count > 2 * len(inp):
        print(indent, "Too many calls")
        exit(1)

    if Start < End:

        PIEnd=Partition(List, Start, End)

        QSort(List,Start,PIEnd)
        QSort(List,PIEnd+1,End)

    print(indent, "ENTER QSort", Start, End, List)    
    indent = indent[2:]

    return List

输出：

   ENTER QSort 0 8 [2, 3, 6, 3, 9, 7, 8, 0, 5]
     ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
       ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
         ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
           ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
             ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
               ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                 ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                   ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                     ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                       ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                         ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                           ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                             ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                               ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                 ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                   ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                     ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                       ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                       Too many calls
于 2020-04-20T17:59:41.490 回答