进入到简单排序的第三个排序，插入排序。其实插入排序，和冒泡，还有选择排序都是比较排序算法的一种，比较效率基本也是O(N²) 但是插入排序，效率基本比冒泡快一倍，选择快一点。
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据的数组，*这里我们可以认为刚开始这个有序数组其实是为空，那么我们排序就是全排序了*
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

可能不太好理解，我们来看几个图

这只是排序的中间状态，我们可以假定刚开始数组有序的部分为空

Paste_Image.png

Paste_Image.png

2.gif

代码如下

//: MARK - 3 插入排序
func insertionSort<T:Comparable>(aArr:[T]) -> [T] {
    var arr = aArr
    for outerIndex in 1..<arr.count { //  在插入排序中OuterIndex左侧是有序的 ， 右侧无需，依次判断 并且向右移动给给被标记变量留出位置
       let temp = arr[outerIndex] // 标记每次需要被插入的数据
       var innerIndex = outerIndex
    
    while innerIndex > 0 && arr[innerIndex - 1 ] >= temp  { // innerIndex , 遍历到最左端也就是0结束，或者是遍历到小于被标记值
            arr[innerIndex] = arr[innerIndex - 1 ]
            innerIndex -= 1 ; // copy 操作
     }
    arr[innerIndex] = temp // 插入被标记值
    
}


return arr

}

   print(insertionSort([9,8,7,6,5,4,3,2,1,0]))

 // 选法的比较效率 O(N²/4) 比冒泡快一倍，比选择快一点

  //对于 基本有序的序列，由于while循环总是为假，算法的效率基本达到O(N²) 对于逆序由于复制太多并没有冒泡快

Paste_Image.png