排序

氣泡排序

這是一個簡單的排序演算法，它反覆遍歷要排序的列表，比較每對相鄰的專案，如果它們的順序錯誤則交換它們。重複通過列表直到不需要交換。雖然演算法很簡單，但對於大多數問題來說它太慢而且不切實際。它具有 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
}