插入排序

插入排序(InsertionSort)，一般也被称为直接插入排序。改变了原有数组数据
对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

1.网上常规示例：

///插入排序
func sortByInsertion2<T: Comparable>(_ a: [T]) -> [T] {
    let maxLenth = a.count
    var temp:[T] = a
    for i in 1..<maxLenth {
        //待插入元素---当前索引元素
        let current = temp[i]
        //当前元素前一个元素 不能为负值
        var preIndex = i - 1;
        while(preIndex >= 0 && temp[preIndex] > current){
            ///此时数组前index都是已经排好序的
            ///当前面preIndex值比当前current对应的值还小的时候 跳出循环
            ///此时数组里面有重复元素 在preIndex和preIndex+1
            ///只是在while语句跳出时候，将current的值赋值给preIndex+1罢了
            temp[preIndex+1] = temp[preIndex]
            preIndex -= 1
        }
        //将current给preIndex+1
        temp[preIndex+1] = current
    }
    return temp
}

2.个人理解示例：

///插入排序
func sortByInsertion1<T: Comparable>(_ a: [T]) -> [T] {
    let maxLenth = a.count
    var temp:[T] = a
    for i in 1..<maxLenth {
        //待插入元素---当前索引元素
        let current = temp[i]
        var mixIndex = -1
        ///前面都是已经排序好的数据
        for j in 0..<i {
            if(temp[j] >= current){
                ///1.将当前元素插入到mixIndex位置
                ///2.数组增加了元素 所以要删除当前current元素 保持数组元素不变
                temp.insert(current, at: j)
                temp.remove(at: i+1)
                break
            }
        }
    }
    return temp
}