參考鏈接

• 交換排序：冒泡排序（Bubble Sort）
• 白話經(jīng)典算法系列之一 冒泡排序的三種實現(xiàn)

基本思想

以從小到大排序舉例

將n個元素看作縱向排列，自上而下對相鄰的兩個數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒

1. 從第一個元素開始依次比較數(shù)組相鄰2個數(shù)，如果前面的元素大于后面的元素，就將二個元素交換
2. 重復(fù)步驟1，這樣每次最大的元素就會被放到末尾
3. 直到最后只剩2個數(shù)做比較，總計n-1趟

初態(tài) 第1趟 第2趟 第3趟 第4趟 第5趟 第6趟 第7趟
 49   38   38   38    38   13   13   13
 38   49   49   49    13   27   27   27 
 65   65   65   13    27   38   38
 97   76   13   27    49   49
 76   13   27   49    49
 13   27   49   65
 27   49   76 
 49   97

算法的實現(xiàn)

extension Array where Element: Comparable {
    mutating func bubbleSort() {
        /*
        1. 整個排序過程共進(jìn)行n-1趟
        2. 每次循環(huán)，會找出最大的元素，放到末尾
        3. 循環(huán)了多少次，末尾就有多少元素已經(jīng)排好序了，內(nèi)循環(huán)只需遍歷前面未排好的元素
        */
        let totalLoop = count - 1
        for loopCount in 0 ..< totalLoop {
            /// 只需遍歷前面未排好的元素
            for current in 0 ..< totalLoop - loopCount {
                let next = current + 1
                /// 比較相鄰的2個元素，并把較大的元素往后面放
                if self[current] > self[next] {
                    swapAt(current, next)
                }
            }
        }
    }
}

冒泡排序算法的改進(jìn)

定義一個標(biāo)志性變量exchange，表示某一趟排序過程中是否有數(shù)據(jù)交換，如果沒有，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序

extension Array where Element: Comparable {
    mutating func bubbleSortBetter() {
        let totalLoop = count - 1
        for loopCount in 0 ..< totalLoop {
            var sorted = true
            /// 只需遍歷前面未排好的元素
            for current in 0 ..< totalLoop - loopCount {
                let next = current + 1
                /// 比較相鄰的2個元素，并把較大的元素往后面放
                if self[current] > self[next] {
                    swapAt(current, next)
                    /// 這次循環(huán)進(jìn)行了數(shù)據(jù)交換，說明沒排好序
                    sorted = false
                }
            }
            
            /// 說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序
            if sorted { break }
        }
    }
}

再做進(jìn)一步的優(yōu)化。如果有100個數(shù)的數(shù)組，僅前面10個無序，后面90個都已排好序且都大于前面10個數(shù)字，那么在第一趟遍歷后，最后發(fā)生交換的位置必定小于10，且這個位置之后的數(shù)據(jù)必定已經(jīng)有序了，記錄下這位置，第二次只要從數(shù)組頭部遍歷到這個位置就可以了。

extension Array where Element: Comparable {
    mutating func bubbleSortBetter2() {
        var unsortedIndexLast = count - 1
        var sorted = false
        
        while !sorted {
            sorted = true
            /// 只需遍歷前面未排好的元素
            for current in 0 ..< unsortedIndexLast {
                let next = current + 1
                if self[current] > self[next] {
                    swapAt(current, next)
                    sorted = false
                    /// 記錄每趟排序中最后一次進(jìn)行交換的位置
                    unsortedIndexLast = current
                }
            }
            
            if sorted { break }
        }
    }
}