###归并排序
- 归并排序的执行流程
- 循环执行:将当前序列平均分割成2个子序列,直至序列中只包含一个元素
- 循环执行:将2个子序列合并成一个有序序列,直到最终合并成一个序列
将序列平均分割成2个子序列:
/// 分割数组 范围 [begin,end)
/// - Parameters:
/// - begin: <#begin description#>
/// - end: <#end description#>
private func divide(begin:Int,end:Int){
guard end - begin > 1 else {
return
}
let mid = (begin + end) >> 1
divide(begin: begin, end: mid)
divide(begin: mid, end: end)
merge(begin: begin, mid: mid, end: end)
}
将2个子序列合并成一个有序序列:
/// 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
/// - Parameters:
/// - begin: <#begin description#>
/// - mid: <#mid description#>
/// - end: <#end description#>
private func merge(begin:Int,mid:Int,end:Int){
/// 分割后左边数组的拷贝
// 2,3,5 (2 | 3,4)
var leftArray:[E] = []
/// 指向左数组当前需要判断大小的指针的索引
var li = 0
/// 指向右数组当前需要判断大小的指针的索引
var ri = mid
/// 左数组结束的索引
let le = mid - begin
/// 右数组结束的索引
let re = end
/// 指向当前数组需要覆盖的索引
var ai = begin
/// 将左边数组拷贝
for i in li..<le {
leftArray.append(self.array[begin + i])
}
/**
合并要注意的几种情况:1.左边先结束,无需做任何操作,即为有序数组
2.右边先结束,将左边未转移的有序数组按顺序替换原数组元素
比较ri和li指向的元素大小,当右侧大ai += 1 ,ri += 1 左侧大ai += 1,li += 1
ri < re : 判断右边数组已经结束,全部使用左边有序数组替换
*/
while li < le {
if ri < re && self.array[ri] < leftArray[li] {
self.array[ai] = self.array[ri]
ai += 1
ri += 1
}else{
self.array[ai] = leftArray[li]
ai += 1
li += 1
}
}
}
- 归并排序的稳定性
- 属于稳定排序
- 归并排序的时间复杂度和空间复杂度
- 时间复杂度
- O(nlogn)
- 空间复杂度
-
O(n/2 + logn) == O(n)
-
n/2用于临时存放左侧数组,logn因为递归调用
-
- 时间复杂度
源码及单元测试:github.com/yukifeng/su…