冒泡排序

参考链接

• 交换排序：冒泡排序（Bubble Sort）
• 白话经典算法系列之一 冒泡排序的三种实现

基本思想

以从小到大排序举例

将n个元素看作纵向排列，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒

1. 从第一个元素开始依次比较数组相邻2个数，如果前面的元素大于后面的元素，就将二个元素交换
2. 重复步骤1，这样每次最大的元素就会被放到末尾
3. 直到最后只剩2个数做比较，总计n-1趟

初态 第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

算法的实现

extension Array where Element: Comparable {
    mutating func bubbleSort() {
        /*
        1. 整个排序过程共进行n-1趟
        2. 每次循环，会找出最大的元素，放到末尾
        3. 循环了多少次，末尾就有多少元素已经排好序了，内循环只需遍历前面未排好的元素
        */
        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)
                }
            }
        }
    }
}

冒泡排序算法的改进

定义一个标志性变量exchange，表示某一趟排序过程中是否有数据交换，如果没有，则说明数据已经按要求排列好，可立即结束排序

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)
                    /// 这次循环进行了数据交换，说明没排好序
                    sorted = false
                }
            }
            
            /// 说明数据已经按要求排列好，可立即结束排序
            if sorted { break }
        }
    }
}

再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

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
                    /// 记录每趟排序中最后一次进行交换的位置
                    unsortedIndexLast = current
                }
            }
            
            if sorted { break }
        }
    }
}