###插入排序
- 插入排序的执行流程
- 将序列分成有序(头部)和无序(尾部)两部分
- 从头开始以此扫描每个元素,找到该元素在头部有序序列中合适的位置插入
for begin in 1..<array.count {
var current = begin
while current > 0 && array[current] < array[current - 1] {
let temp = array[current]
array[current] = array[current - 1]
array[current - 1] = temp
current -= 1
}
}
- 插入排序的优化
- 将交换目标元素和其余元素的操作改为挪动部分有序元素,后一次插入操作将目标元素插入到合适位置
for begin in 1..<array.count {
var current = begin
let element = array[current]
while current > 0 && element < array[current - 1]{
array[current] = array[current - 1]
current -= 1
}
array[current] = element
}
- 使用二分查找寻找目标元素应插入的位置
/// 将source位置的元素插入到dest的位置
/// - Parameters:
/// - source: <#source description#>
/// - dest: <#dest description#>
private func insert(source:Int,dest:Int){
let element = array[source]
var i = source
while i > dest {
array[i] = array[i - 1]
i -= 1
}
array[dest] = element
}
/// 二分查找元素应插入的位置 范围是[0,target)
/// - Parameters:
/// - array: 数组
/// - target: 目标元素索引
/// - Returns: 元素插入的下标
private func search(target:Int) -> Int{
guard array.count > 0 else {
return 0
}
var begin = 0
var end = target
while begin < end {
let mid = (begin + end) >> 1
if array[target] < array[mid]{
end = mid
}else {
begin = mid + 1
}
}
return begin
}
-
插入排序的稳定性
- 属于稳定的排序算法
-
插入排序的时间复杂度和空间复杂度
- 时间复杂度
- 需要遍历两轮,时间复杂度为O(n^2)
- 使用二分查找后减少了比较次数,但时间复杂度仍未O(n^2)
- 空间复杂度
-
O(1)
-
属于原地算法
-
- 时间复杂度
源码及单元测试:github.com/yukifeng/su…