插入排序
时间复杂度：O(n²)
稳定性：稳定
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
算法步骤
- 将第1个元素作为有序数列，从第2个元素开始遍历，将遍历到的元素插入到有序数列的适当位置；
从后往前扫描有序数列，如果 待插入元素 较小，则继续往前扫描，直至前面没有比 待插入元素 大的元素为止，即完成一次插入 - 重复上面操作，直至待排序元素都插入到适当的位置；
insertionSort.gif
时间复杂度分析
假设序列有n个元素，n>1，根据算法步骤，第1轮取第2个元素插入到已排序数列（1个元素）中，第2轮取第3个元素插入到已排序数列（有2个元素）中，… 第(n-1)轮取第n个元素插入到已排序数列（有(n-1)个元素）中。
函数表达式为：
f(n) = 1+2+…+(n-1)
f(n) = n*(n-1)/2
f(n) = (n²-n)/2
用大O表示法，忽略常量、低阶和常数系数。
时间复杂度为：O(n²)
算法代码（Swift）
func insertionSort(numbers: [Int]) -> [Int] {
var sortedNumbers = numbers
for i in 1..<sortedNumbers.count {
let temp = sortedNumbers[i]
print("\n\(sortedNumbers) (\(i)th circle begin, num = \(temp)")
for j in (0..<i).reversed() {
if temp < sortedNumbers[j] {
sortedNumbers.swap(j, j+1)
print("swap at \(j) and \(j+1)")
} else {
break
}
}
}
return sortedNumbers
}
let numbers = [1, 4, 3, 2, 0, 5, 6, 7, 8, 9]
print("\(numbers) (random numbers)")
let sortedNumbers = insertionSort(numbers: numbers)
print("\n\(sortedNumbers) (insertion sort result)")
终端打印：
[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (random numbers)
[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (1th circle begin, num = 4
[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (2th circle begin, num = 3
swap at 1 and 2
[1, 3, 4, 2, 0, 5, 6, 7, 8, 9] (3th circle begin, num = 2
swap at 2 and 3
swap at 1 and 2
[1, 2, 3, 4, 0, 5, 6, 7, 8, 9] (4th circle begin, num = 0
swap at 3 and 4
swap at 2 and 3
swap at 1 and 2
swap at 0 and 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (5th circle begin, num = 5
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (6th circle begin, num = 6
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (7th circle begin, num = 7
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (8th circle begin, num = 8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (9th circle begin, num = 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (insertion sort result)
