Swift：在合併排序中計數交換

Question

我試圖計算合併排序中的交換。這似乎是一個非常簡單的命題，但似乎對我的邏輯有問題。

這裏就是我想我的遞增計數我的代碼的相關部分：

while leftIndex < leftPile.count && rightIndex < rightPile.count { 
     if leftPile[leftIndex] < rightPile[rightIndex] { 
      // nothing swapped here 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
     } else if leftPile[leftIndex] > rightPile[rightIndex] { 
      orderedPile.append(rightPile[rightIndex]) 
      // item taken from right pile == swapped -> increment swapCount 
      swapCount += 1 
      rightIndex += 1 
     } else { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
      // item taken from left pile == swapped -> increment swapCount 
      swapCount += 1 
      orderedPile.append(rightPile[rightIndex]) 
      rightIndex += 1 
     } 
    } 

出於某種原因，我就指望5個互換與下面的數組：

unsortedArray = [2, 1, 3, 1, 2] 
sortedArray = [1, 1, 2, 2, 3] 
swapCount = 5 

這是我的滿級：

class MergeSortWithCounter { 

    var swapCount: Int64 

    init() { 
     swapCount = 0 
    } 

    func mergeSort<T: Comparable>(_ array: [T]) -> [T] { 
     guard array.count > 1 else { return array } 
     let middleIndex = array.count/2 
     let leftArray = mergeSort(Array(array[0..<middleIndex])) 
     let rightArray = mergeSort(Array(array[middleIndex..<array.count])) 
     return merge(leftPile: leftArray, rightPile: rightArray) 
    } 

    func merge<T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] { 

     var leftIndex = 0 
     var rightIndex = 0 
     var orderedPile = [T]() 
     if orderedPile.capacity < leftPile.count + rightPile.count { 
      orderedPile.reserveCapacity(leftPile.count + rightPile.count) 
     } 

     while leftIndex < leftPile.count && rightIndex < rightPile.count { 
      if leftPile[leftIndex] < rightPile[rightIndex] { 
       // nothing swapped here 
       orderedPile.append(leftPile[leftIndex]) 
       leftIndex += 1 
      } else if leftPile[leftIndex] > rightPile[rightIndex] { 
       orderedPile.append(rightPile[rightIndex]) 
       // item taken from right pile == swapped -> increment swapCount 
       swapCount += 1 
       rightIndex += 1 
      } else { 
       orderedPile.append(leftPile[leftIndex]) 
       leftIndex += 1 
       // item taken from left pile == swapped -> increment swapCount 
       swapCount += 1 
       orderedPile.append(rightPile[rightIndex]) 
       rightIndex += 1 
      } 
     } 

     while leftIndex < leftPile.count { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
     } 

     while rightIndex < rightPile.count { 
      orderedPile.append(rightPile[rightIndex]) 
      rightIndex += 1 
     } 

     return orderedPile 
    } 
} 

我知道我失去了一些東西超級簡單，但我花了更多的時間THA我在乎承認弄清楚我的錯誤在哪裏。

感謝您的閱讀！

Answer 1

你在同等情況下，交換時你沒有到：

 if leftPile[leftIndex] < rightPile[rightIndex] { 
      // nothing swapped here 

你的意思

 if leftPile[leftIndex] <= rightPile[rightIndex] { 
      // nothing swapped here