算法:插入排序

let numbersArray = [1, 4, 6, 2, 8]
let sortArray = insertionSort(elements: numbersArray)

// 这个函数里有两个循环
func insertionSort(elements: [Int]) -> [Int] {
    // 不能直接修改参数elements
    // 所以使用array这个临时变量来进行排序
    var array = elements
    
    // 外部循环遍历数组中的每个元素,注意:索引从1开始
    for i in 1..<array.count {
        // 比较的目标值
        let compareValue = array[i]
        // 临时索引,内循环需要用
        var j = i
        
        // 取出需要比较的值2,这个值跟前边一个比较,如果比前边的小
        // 那么先让当前对应的索引的值,修改为前边的值(比如2与6比较,array[3]=6)
        // 临时变量j同时-1,继续拿着2跟前边的4进行比较
        // 2<4,所以修改当前对应的索引所对应的值为4(array[2]=4)
        // 临时变量j同时-1,
        // 2>1,找到了对应的位置索引,排序array[1] = 2
        
        // 内循环:对应外循环的目标值compareValue,与之前的元素进行比较
        while compareValue < array[j-1] && j > 0{
            array[j] = array[j-1]
            j -= 1
        }
        // [1, 4, 6, 2, 8]
        // 如果目标值(比如4)compareValue > array[j-1](比如1)
        // 那么array[1] = compareValue,直接排序,然后进入下一个外循环,去比较6
        array[j] = compareValue
    }
    return array
}