ARTS Week Six
divide and conquer
- 把数字都放到一个未排序的数组里
- 把这个数组分割成两个, 将分割后的数组继续分割直到没有可以分割的数组。最后，将会拥有 n 个只有一个数字在里面的数组
- 开始通过顺序配对将它们合并在一起。在每次合并期间，将内容按排序顺序排列。这很容易，因为每个单独的堆已经排序。
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
let middleIndex = array.count / 2 // 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4
return merge(leftPile: leftArray, rightPile: rightArray) // 5
}
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var orderedPile = [Int]()
// 3
/**
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l -->r
again
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l -->r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
-->l r
**/
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}