Swift 冒泡排序及优化

冒泡排序是大家都常用的排序方法

冒泡排序算法的运作如下：（从后往前）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序是稳定的排序算法

时间复杂度
冒泡排序的最佳时间复杂度为O(n)，即初始状态就是排好序的。
冒泡排序的最坏时间复杂复杂度为O(n²)，即初始状态就是逆序的。
冒泡排序的平均时间复杂复杂度为O(n²)

根据这个原理代码如下:

    //冒泡排序
    func bubbleSort(_ nums: inout [Int]) {
        let n = nums.count
        for i in 0..<n {
            for j in 0..<(n - 1 - i) {
                if nums[j] > nums[j + 1] {
                    nums.swapAt(j, j + 1)
                }
            }
        }
    }

   //使用
    var nums = [1,3,6,9,0,5,2,4,8,7]
    bubbleSort(&nums)
    print(nums) 
    // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

冒泡排序优化一：
当发现在某一趟排序中发现没有发生交换，则说明排序已经完成，所以可以在此趟排序后结束排序。在每趟排序前设置flag，当其未发生改变时，终止算法；

代码如下：

     //冒泡排序 优化一（外层优化）
    func bubbleSort1(_ nums: inout [Int]) {
        let n = nums.count
        for i in 0..<n {
            var flag = true
            for j in 0..<(n - 1 - i) {
                if nums[j] > nums[j + 1] {
                    nums.swapAt(j, j + 1)
                    flag = false
                }
            }
            if flag {
                break
            }
        }
    }
    //使用
    var nums = [1,3,6,9,0,5,2,4,8,7]
    bubbleSort1(&nums)
    print(nums) 
    // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

冒泡排序优化二：
每趟排序中，最后一次发生交换的位置后面的数据均已有序，所以我们可以记住最后一次交换的位置来减少排序的趟数。

    //冒泡排序 优化二（内层优化）
    func bubbleSort2(_ nums: inout [Int]) {
        let n = nums.count
        var swap = 0 //swap变量用来标记循环里最后一次交换的位置
        var k = n - 1 //内循环判断条件
        for _ in 0..<n {
            var flag = true
            for j in 0..<k {
                if nums[j] > nums[j + 1] {
                    nums.swapAt(j, j + 1)
                    flag = false
                    swap = j
                }
            }
            
            k = swap
            
            if flag {
                break
            }
        }
    }
    //使用
    var nums = [1,3,6,9,0,5,2,4,8,7]
    bubbleSort2(&nums)
    print(nums)
    // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

那么现在用上面的代码做个测试：

1.在排序算法外层排序记录次数

//冒泡排序
func bubbleSort(_ nums: inout [Int]) {
    let n = nums.count
    var count = 0
    for i in 0..<n {
        count = I
        for j in 0..<(n - 1 - i) {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
            }
        }
    }
    print(count)
}

//使用
var nums = [1,3,6,7,9,0,5,2,4,8]
bubbleSort(&nums)

另外两个算法也一样这么处理，发现简单的冒泡排序外层运行10次，而优化后的代码运行6次。

2.在排序算法内层排序记录次数
直接打印k值和原来的（n - 1 - i）来比较

//冒泡排序 优化二（内层优化）
func bubbleSort2(_ nums: inout [Int]) {
    let n = nums.count
    var swap = 0 //swap变量用来标记循环里最后一次交换的位置
    var k = n - 1 //内循环判断条件
    var count = 0
    for i in 0..<n {
        count = i
        var flag = true
        for j in 0..<k {
            
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
                flag = false
                swap = j
            }
        }
        
        k = swap
        
        print("k:",k)
        print("n:",n - i - 1)
        
        if flag {
            break
        }
    }
    print(count)
}
//使用
var nums2 = [1,3,6,7,9,0,5,2,4,8]
bubbleSort2(&nums2)

结果如下：

内层循环次数比较

根据结果可以发现，内层的循环减少的次数还是很多的。