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(leftArray, rightArray)
}
func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
var leftIndex = 0
var rightIndex = 0
var orderedArray: [T] = []
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)
leftIndex += 1
orderedArray.append(rightElement)
rightIndex += 1
}
}
while leftIndex < left.count {
orderedArray.append(left[leftIndex])
leftIndex += 1
}
while rightIndex < right.count {
orderedArray.append(right[rightIndex])
rightIndex += 1
}
return orderedArray
}
Swift Merge Sort
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到s...
- 排序的方法有很多种，今天来写一下Insertion Sort和Merge Sort的效率问题。 要讨论两种排序法的...
- 耗时 公式中 n 为参与排序的个数，T(n) 为排序时间。 分析 由上面可以看出当 n 足够大时 n^2 会远远大...
