如何在python中添加合并排序的比较计数器？

Question

我使用的代码如下。在

我想在代码中添加一个比较计数器，但是我现在的比较计数器将显示与元素数量相同的数字。在

def MergeSort(argShuffledList):
    intNumOfComp = 0
    if len(argShuffledList)>1:
        intMidValue = len(argShuffledList)//2
        listLeftHalf = argShuffledList[:intMidValue]
        listRightHalf = argShuffledList[intMidValue:]

        MergeSort(listLeftHalf)
        MergeSort(listRightHalf)

        i=0
        j=0
        k=0
        while i < len(listLeftHalf) and j < len(listRightHalf):
            if listLeftHalf[i] < listRightHalf[j]:
                argShuffledList[k]=listLeftHalf[i]
                i=i+1
                intNumOfComp += 1
            else:
                argShuffledList[k]=listRightHalf[j]
                j=j+1
                intNumOfComp += 1

            k=k+1

        while i < len(listLeftHalf):
            argShuffledList[k]=listLeftHalf[i]
            i=i+1
            k=k+1
            intNumOfComp += 1

        while j < len(listRightHalf):
            argShuffledList[k]=listRightHalf[j]
            j=j+1
            k=k+1
            intNumOfComp += 1

    return argShuffledList, "Comparison Count: " + str(intNumOfComp)

Answer 1

因为你没有把列表的左右两部分进行比较。这是经过改造的正确代码。在

def MergeSort(argShuffledList):
    intNumOfComp = 0

    if len(argShuffledList)>1:
        intMidValue = len(argShuffledList)//2
        listLeftHalf = argShuffledList[:intMidValue]
        listRightHalf = argShuffledList[intMidValue:]

        left_part = MergeSort(listLeftHalf)
        right_part = MergeSort(listRightHalf)

        intNumOfComp += left_part[1] + right_part[1]

        i=0
        j=0
        k=0
        while i < len(listLeftHalf) and j < len(listRightHalf):
            intNumOfComp += 1
            if listLeftHalf[i] < listRightHalf[j]:
                argShuffledList[k]=listLeftHalf[i]
                i =i+1

            else:
                argShuffledList[k]=listRightHalf[j]
                j=j+1

            k=k+1

        while i < len(listLeftHalf):
            argShuffledList[k]=listLeftHalf[i]
            i=i+1
            k=k+1
            intNumOfComp += 1

        while j < len(listRightHalf):
            argShuffledList[k]=listRightHalf[j]
            j=j+1
            k=k+1
            intNumOfComp += 1

    return argShuffledList, intNumOfComp