排序

冒泡排序

这是一个简单的排序算法，它反复遍历要排序的列表，比较每对相邻的项目，如果它们的顺序错误则交换它们。重复通过列表直到不需要交换。虽然算法很简单，但对于大多数问题来说它太慢而且不切实际。它具有 O(n2) 的复杂性，但被认为比插入排序慢。

extension Array where Element: Comparable {

func bubbleSort() -> Array<Element> {
    
    //check for trivial case
    guard self.count > 1 else {
        return self
    }
    
    //mutated copy
    var output: Array<Element> = self
    
    for primaryIndex in 0..<self.count {
        let passes = (output.count - 1) - primaryIndex
        
        //"half-open" range operator
        for secondaryIndex in 0..<passes {
            let key = output[secondaryIndex]
            
            //compare / swap positions
            if (key > output[secondaryIndex + 1]) {
                swap(&output[secondaryIndex], &output[secondaryIndex + 1])
            }
        }
    }
    
    return output
}

}

插入排序

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

选择排序

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

func selectionSort() - > Array {//检查琐碎的案例保护 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 
}

快速排序 - O（n log n）复杂时间

Quicksort 是一种先进的算法。它具有 O（n log n）的时间复杂度，并采用分而治之的策略。这种组合产生了先进的算法性能。Quicksort 首先将一个大数组分成两个较小的子数组：低元素和高元素。Quicksort 然后可以递归地对子数组进行排序。

步骤是：

从数组中选择一个称为 pivot 的元素。

对数组重新排序，使得值小于 pivot 的所有元素都在 pivot 之前，而值大于 pivot 的所有元素都在它之后（相同的值可以是任意一种）。在此分区之后，枢轴处于其最终位置。这称为分区操作。

递归地将上述步骤应用于具有较小值的元素的子数组，并分别应用于具有较大值的元素的子数组。

mutating func quickSort() - > Array {

func qSort(start startIndex: Int, _ pivot: Int) {
    
    if (startIndex < pivot) {
        let iPivot = qPartition(start: startIndex, pivot)
        qSort(start: startIndex, iPivot - 1)
        qSort(start: iPivot + 1, pivot)
    }
}
qSort(start: 0, self.endIndex - 1)
return self
}

mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {

var wallIndex: Int = startIndex

//compare range with pivot
for currentIndex in wallIndex..<pivot {
    
    if self[currentIndex] <= self[pivot] {
        if wallIndex != currentIndex {
            swap(&self[currentIndex], &self[wallIndex])
        }
        
        //advance wall
        wallIndex += 1
    }
}
    //move pivot to final position
    if wallIndex != pivot {
        swap(&self[wallIndex], &self[pivot])
    }
    return wallIndex
}