插入排序

插入排序是计算机科学中更基本的算法之一。插入排序通过迭代集合对元素进行排名，并根据元素的值定位元素。该集合分为有序和未分类的一半，并重复，直到所有元素都被排序。插入排序具有 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
}
}