swift中的归并排序算法

Question

我一直在试图弄清楚为什么我的代码不能工作。我似乎想不通了。我已经检查过代码引用，但它们都使用"mergedArr.removeFirst()“，这在计算上比较昂贵。

func mergeSort(arr: [Int]) -> [Int] {
    
    guard arr.count > 1 else {
        return arr
    }
    
    let middleIndex = arr.count / 2
    let leftArray = Array(arr[0..<middleIndex])
    let rightArray = Array(arr[middleIndex..<arr.count])
    
    
    return merge(left:mergeSort(arr: leftArray), right: mergeSort(arr: rightArray))
}

func merge(left: [Int], right: [Int]) -> [Int] {
    
    var leftIndex = 0
    var rightIndex = 0
    var mergedArr = [Int]()
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            mergedArr.append(left[leftIndex])
            leftIndex += 1
        } else if left[leftIndex] > right[rightIndex]{
            mergedArr.append(right[rightIndex])
            rightIndex += 1
        } else {
            mergedArr.append(left[leftIndex])
            leftIndex += 1
            mergedArr.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
       return mergedArr
}

Answer 1

用更简单的版本替换while- loop的内部结构

 while leftIndex < left.count && rightIndex < right.count {
    if left[leftIndex] <= right[rightIndex] {
        mergedArr.append(left[leftIndex])
        leftIndex += 1
    } else {
        mergedArr.append(right[rightIndex])
        rightIndex += 1
    }
 }

而你忘记了数组的其余部分：

 while leftIndex < left.count {
        mergedArr.append(left[leftIndex])
        leftIndex += 1
 }
 while rightIndex < right.count {
        mergedArr.append(right[rightIndex])
        rightIndex += 1
    }

为什么？当你合并两个数组时，一个数组的尾部可能还没有被处理。例如，合并[1 3 5] and [1 2]。在复制到结果循环之后，第二个数组完成(rightIndex变为等于right.count)，主while- [1 1 2]停止。但是[3,5] piece呢？

Answer 2

它不起作用，因为您忘记将左子数组和右子数组中的剩余数据添加到有序数组中。merge方法应该如下所示。

func merge<>(_ left: [Int], _ right: [Int]) -> [Int] {
  var leftIndex = 0
  var rightIndex = 0
  var orderedArray = [Int]()

  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]

    if leftElement < rightElement {
      orderedArray.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      orderedArray.append(rightElement)
      rightIndex += 1
    } else {
      orderedArray.append(leftElement)
      orderedArray.append(rightElement)
      leftIndex += 1
      rightIndex += 1
    }
  }

  while leftIndex < left.count {
    orderedArray.append(left[leftIndex])
    leftIndex += 1
  }

  while rightIndex < right.count {
    orderedArray.append(right[rightIndex])
    rightIndex += 1
  }

  return orderedArray
}

Answer 3

考虑数据是仅保留在left上还是仅保留在right上。

public func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    if array.count < 2 {
        return array
    }
    
    let mid = array.count / 2
    
    let left = [T](array[0..<mid])
    let right = [T](array[mid..<array.count])

    return merge(left, right)
}


private func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    var tempList = [T]()
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            tempList.append(left[leftIndex])
            leftIndex += 1
            
        } else if left[leftIndex] > right[rightIndex] {
            tempList.append(right[rightIndex])
            rightIndex += 1
        }
        else {
            tempList.append(left[leftIndex])
            tempList.append(right[rightIndex])
            leftIndex += 1
            rightIndex += 1
        }
    }
    
    //Don't miss this part.
    while leftIndex < left.count {
        tempList.append(left[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < right.count {
        tempList.append(right[rightIndex])
        rightIndex += 1
    }

    return tempList
}