参考链接
基本思想
每次将一个待排序的元素，插入到前面已经排好序的子序列中，直到全部元素插入完成为止。
打过扑克牌的人都应该能够秒懂！！！
插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。
算法的实现
extension Array where Element: Comparable {
mutating func insertSort() {
/*
1. 整个排序过程共进行n-1趟
2. 每次取一个元素插入到前面排好序的数组中
*/
for i in 1 ..< count {
let insert = self[i]
var j = i
while j >= 1, insert < self[j - 1] {
self[j] = self[j - 1]
j -= 1
}
self[j] = insert
}
}
}
改进
将 array[j] 插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。
如果 array[j] 前一个数据 array[j-1] > array[j]，就交换 array[j] 和 array[j-1]，再 j--
直到 array[j-1] <= array[j]。这样也可以实现将一个新数据并入到有序区间。
extension Array where Element: Comparable {
mutating func insertSort2() {
/// 每次取一个元素插入
for insert in 1 ..< count {
var current = insert
while current > 0 {
let prev = current - 1
/// 如果插入元素小于前一个元素就交换2者，直到找到合适插入位置
if self[current] < self[prev] {
swapAt(current, prev)
current -= 1
} else {
break
}
}
}
}
}
