如何在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