冒泡排序

0.冒泡.jpg

思想

从第一个元素开始比较相邻两个元素的大小，如果后面的元素小，则交换两个元素的位置，直到所有相邻的元素都交换完成，最大的元素放到了最后。
每完成一次上面所说的比较之后，再次参与比较的数组元素就会少一个（即最后一个最大元素）

时间复杂度

O(n^2)

代码

struct Bubble {
    
    #warning("如何使用一个泛型")
    // 冒泡排序时间复杂度是O(n^2)
    static func sort(array: inout [Int]) {
        for i in (1..<array.count).reversed() { // 倒序遍历， 内层循环每循环一次，参与比较的元素就少一个，因为最大的元素已经排到了最后
            for j in 0..<i {
                let a = array[j]
                let b = array[j + 1]
                let result = compare(a: a, b: b)
                if result == true {
                    exchange(array: &array, aIndex: j, bIndex: j + 1)
                }
            }
        }
    }
    
    /// 比较大小
    static func compare(a: Int, b: Int) -> Bool {
        if a > b {
            return true
        } else {
            return false
        }
    }
    
    /// 交换位置
    static func exchange( array: inout [Int], aIndex: Int, bIndex: Int) {
        let temp = array[aIndex]
        array[aIndex] = array[bIndex]
        array[bIndex] = temp
    }
    
}