Swift 5.3 排序算法 O(n²)

时间复杂度O(n²)的排序算法

以下排序算法的时间复杂度都是O(n²)

冒泡排序

从后往前依次遍历数组中的元素，两个相邻元素，如果后面的元素比前面的元素小，就交换他们在数组中的位置，最后一个元素最多可以被交换n-1次，遍历一次之后，就找到了全部元素中的最小元素，然后再进行一次遍历，找第二小的元素。表现形式就是2个for循环。

public func bubbleSort<Element: Comparable>(_ array: inout [Element]) {
    guard array.count >= 2 else { return }
    for end in (1 ..< array.count).reversed() {
        var swapped = false
        for current in 0 ..< end {
            if array[current] > array[current + 1] {
                array.swapAt(current, current + 1)
                swapped = true
            }
        }

        if !swapped {
            return
        }
    }
}

选择排序

从前向后遍历整个数组，取得第一个元素，与之后的元素进行比较，得到最小元素的index，直到比较n-1次，会得到整个数组的最小值，交换最小值和第一个元素的位置。之后剩下n-1个元素，还是这样进行就可以找到第二小的元素，表现形式是2个for循环。

public func selectionSort<Element: Comparable>(_ array: inout [Element]) {
    guard array.count >= 2 else { return }
    for current in 0..<(array.count - 1) {
        var lowest = current
        for other in (current + 1)..<array.count {
            if array[lowest] > array[other] {
                lowest = other
            }
        }
        if lowest != current {
            array.swapAt(lowest, current)
        }
    }
}

插入排序

从前向后遍历，第一次取第二个元素和第一个元素比较，确定前两个元素的顺序，然后再去确定前三个元素的顺序，表现是2个for循环，外循环每执行一次，整个数组的前部分都是已经排好顺序的了，内循环用来确定下一个元素所在的顺序。

public func insertionSort<Element: Comparable>(_ array: inout [Element]) {
    guard array.count >= 2 else {
        return
    }

    for current in 1..<array.count {
        for shifting in (1..<current).reversed() {
            if array[shifting] < array[shifting - 1] {
                array.swapAt(shifting, shifting - 1)
            } else {
                break
            }
        }
    }
}