Блог

Я пытался понять, почему мой код не работает. Кажется, я не могу этого понять. Я проверил наличие ссылок на код, но все они используют «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 amp;amp; 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
}
 

Замените внутренние компоненты цикла while на более простую версию

  while leftIndex < left.count amp;amp; 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] . После копирования в результат [1 1 2] второй массив завершается ( rightIndex становится равным right.count ) и основной цикл while останавливается. Но как насчет [3,5] piece?

Он не работает, потому что вы забыли добавить в свой упорядоченный массив оставшиеся данные в левом и правом подмассивах. Метод слияния должен выглядеть следующим образом.

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

  while leftIndex < left.count amp;amp; 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
}
 

Подумайте, остаются ли данные 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 amp;amp; 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
}