选择排序

选择排序因其简单性而着称。它从数组中的第一个元素开始,将其值保存为最小值(或最大值,具体取决于排序顺序)。然后它通过数组进行迭代,并将 min 值替换为在路上找到的 min 之后的任何其他值。然后将该最小值放在数组的最左边部分,并从下一个索引重复该过程,直到数组结束。选择排序具有 O(n2) 的复杂度,但它被认为比它的对应物慢 - 选择排序。

func selectionSort() -> 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 {
        var minimum = primaryindex
        var secondaryindex = primaryindex + 1
         
        while secondaryindex < output.count {
            //store lowest value as minimum
            if output[minimum] > output[secondaryindex] {
                minimum = secondaryindex
            }
            secondaryindex += 1
        }
         
        //swap minimum value with array iteration
        if primaryindex != minimum {
            swap(&output[primaryindex], &output[minimum])
        }
    }
     
    return output
}