插入排序

插入排序是電腦科學中更基本的演算法之一。插入排序通過迭代集合對元素進行排名，並根據元素的值定位元素。該集合分為有序和未分類的一半，並重復，直到所有元素都被排序。插入排序具有 O(n2) 的複雜度。你可以將其放在副檔名中，如下面的示例所示，或者你可以為其建立方法。

extension Array where Element: Comparable {

func insertionSort() -> Array<Element> {
    
    //check for trivial case
    guard self.count > 1 else {
        return self
    }
    
    //mutated copy
    var output: Array<Element> = self
    
    for primaryindex in 0..<output.count {
        
        let key = output[primaryindex]
        var secondaryindex = primaryindex
        
        while secondaryindex > -1 {
            if key < output[secondaryindex] {
                
                //move to correct position
                output.remove(at: secondaryindex + 1)
                output.insert(key, at: secondaryindex)
            }
            secondaryindex -= 1
        }
    }
    
    return output
}
}