冒泡排序

冒泡排序是一种时间复杂度为 O(N^2) 的慢速排序。每一次遍历数组，比较相邻两元素的大小，将较大者换到右边。也就是说，每一次遍历都会选出未排序的元素中的最大值。

func bubbleSort<T: Comparable>(array: inout[T]) -> [T]{
    for i in 0..<array.count - 1 {
        for j in 0..<array.count - 1 - i {
            if array[j] > array[j + 1] {
                let temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
            }
        }
    }
    return array
}

插入排序

插入排序是一种 O(N^2) 的排序方法，思路是将未排序的元素插入到已排序的数组当中合适的位置。

func insertionSort<T: Comparable>(array: inout[T]) -> [T]{
    for i in 1..<array.count {
        // 当前待插入的元素
        let insertion = array[i]
        // 从后往前遍历之前的所有元素
        for j in (0..<i).reversed() {
            // 如果 insertion 小于 array[j]，那么 array[j] 向右移动一位
            if insertion < array[j] {
                // move array[j] to right by 1
                array[j + 1] = array[j]
                array[j] = insertion
            // 如果不小于，那么位置正确，插入并且跳出循环
            } else {
                array[j + 1] = insertion
                break
            }
        }
    }
    return array
}

选择排序

选择排序的性能不如插入排序，时间复杂度依然是 O(N^2) 。思路是每一次遍历数组，都选出数组的最小值。与冒泡排序不同的是，选择排序通过遍历所有未排序元素来选出最小值；而冒泡排序是通过两两比较并且交换来滤出最小值/最大值。

func selectionSort<T: Comparable>(array: inout[T]) -> [T]{
    guard array.count > 1 else {return array}
    for i in 0..<array.count {
        // 选出最小值
        var minIndex = i
        for j in i + 1 ..< array.count {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }
        // 交换两个值
        let temp = array[minIndex]
        array[minIndex] = array[i]
        array[i] = temp
        // 也可以用 swift 元组来交换
        // (array[minIndex], array[i]) = (array[i], array[minIndex])
    }
    return array
}

快速排序

快速排序是一种时间复杂度为 O(Nlog N)* 的算法，其思路是首先选定某一个位置的值作为支点，然后将数组一分为二，大于支点的元素和小于支点的元素。将这个过程递归直到不可再分为止。然后将整个递归的结果串联起来便是排好序的数组。

func quickSort<T: Comparable>(array: [T]) -> [T] {
    guard array.count > 0 else {
        return array
    }

    // 支点
    let pivot = array[array.count / 2]

    // 小于、等于、大于支点
    let less = array.filter{ $0 < pivot }
    let equal = array.filter{ $0 == pivot }
    let greater = array.filter{ $0 > pivot }

    // 递归并且拼接，加号是 swift 当中拼接数组的方法
    return quickSort(array: less) + equal + quickSort(array: greater)
}

以上代码选取支点的方式是取中间元素，根据特殊的情况选择一个合适的支点可以对性能有很大提升。

代码中使用 swift 中的 filter 闭包来实现对数组中元素的筛选，最后返回值是将三个数组拼接在一起。

下面我们使用一张图来说明整个过程：

示例

从图中可以看出，如果我们的支点选择的不够恰当，比如恰好选择的是最大值或者最小值，那么整个数将会失衡。如果大多数元素都集中在一侧的子节点的话，那么会增加无用的递归次数。

归并排序

归并排序的思路是将原数组进行二分分割，直到不可分。然后再调用一个合并函数将这些分割后的数组进行有序的合并。时间复杂度为 O(NlogN)*。

归并排序

func mergeSort<T: Comparable>(array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    // 一分为二
    let mid = array.count / 2
    let leftArray = mergeSort(array: Array(array[0..<mid]))
    let rightArray = mergeSort(array: Array(array[mid..<array.count]))
    return merge(leftPile: leftArray, rightPile: rightArray)
}

func merge<T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] {
    //  两个索引，用于记录两边数组的位置
    var leftIndex = 0
    var rightIndex = 0
    
    // 归并的结果
    var result = [T]()
    
    // 此循环将两边的数组的元素有序的往 result 数组中添加元素
    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        // 左 < 右
        if leftPile[leftIndex] < rightPile[rightIndex] {
            result.append(leftPile[leftIndex])
            leftIndex += 1
        // 左 > 右
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            result.append(rightPile[rightIndex])
            rightIndex += 1
        // 左 = 右
        } else {
            // 左右都放
            result.append(leftPile[leftIndex])
            leftIndex += 1
            result.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }
    
    // 处理左侧剩余的元素，比如右侧已经空了，但左侧还有很多元素
    while leftIndex < leftPile.count {
        result.append(leftPile[leftIndex])
        leftIndex += 1
    }
    // 处理右侧剩余的元素
    while rightIndex < rightPile.count {
        result.append(rightPile[rightIndex])
        rightIndex += 1
    }
    
    return result
}

计数排序

计数排序的思路是创建另一个数组来记录原数组中数据出现的位置，然后再按照顺序还原出有序数组。时间复杂度为O(n + k)，k 代表创建一个 counting 数组需要用的时间。计数排序是一种典型的牺牲空间复杂度来换取时间复杂度的算法，其空间复杂度为O(2n)。

let array = [8, 4, 6, 9, 1, 3, 5, 8, 2, 10]

func countingSort(array: [Int]) -> [Int]{
    // 第一步：创建一个用于计数的数组来保存原数组数据的出现次数。
    let max = array.max() ?? 0
    var countArray = [Int](repeating: 0, count: max + 1)
    for each in array {
        countArray[each] += 1
    }
    print(countArray) // [0, 1, 1, 1, 1, 1, 1, 0, 2, 1, 1]
    
    // Step 2: Sum up.
    // 第二步：横着求和，每一个元素等于之前的元素的和。
    for index in 1 ..< countArray.count {
        countArray[index] += countArray[index - 1]
    }
    print(countArray) // [0, 1, 2, 3, 4, 5, 6, 6, 8, 9, 10]
    
    // Step 3: Place. 
    // 第三步：放置。
    var sortedArray = [Int](repeating: 0, count: array.count)
    for each in array {
        countArray[each] -= 1
        sortedArray[countArray[each]] = each
    }
    return sortedArray
}

print(countingSort(array: array)) // [1, 2, 3, 4, 5, 6, 8, 8, 9, 10]

附：排序算法度量总结图

排序算法度量