排序算法-冒泡、选择排序

风吹夏天 2020-04-19

冒泡排序(升序为例)

思路:
1. 从头开始比较每一对相临的元素,其后者比前者大则交换,直到一轮比较结束
2. 排除1中找到最大的元素,重复1的步骤

class BubbleSort {
    
    var array = [5, 7, 2, 8, 9, 4, 7, 3, 2]
    
    // 基本版本
    func sort() {
        for end in (1 ..< array.count).reversed() {
            for begin in 1 ... end {
                if array[begin] < array[begin - 1] {
                    let tmp = array[begin]
                    array[begin] = array[begin - 1]
                    array[begin - 1] = tmp
                }
            }
        }
    }
    
    // 如果在某一趟比较后,序列就变得完全有序,此时就没有必要再继续比较下去
    func sort2() {
        for end in (1 ..< array.count).reversed() {
            var sorted = true
            for begin in 1 ... end {
                if array[begin] < array[begin - 1] {
                    let tmp = array[begin]
                    array[begin] = array[begin - 1]
                    array[begin - 1] = tmp
                    // 如果来到这里表明数列不是完全有序
                    sorted = false
                }
            }
            if sorted { break }
        }
    }
    
    // 如果数列在尾部已经有序(部分有序)
    func sort3() {
        for var end in (1 ..< array.count).reversed() {
            var endIndex = 1
            for begin in 1 ... end {
                if array[begin] < array[begin - 1] {
                    let tmp = array[begin]
                    array[begin] = array[begin - 1]
                    array[begin - 1] = tmp
                    // 如果不到这里表明在上次比较后,begin后面就是全部有序
                    endIndex = begin
                }
            }
            end = endIndex
        }
        
    }
}

* 最坏、平均时间复杂度:O(n^2),最好时间复杂度:O(n)

* 空间复杂度: O(1)

* 稳定性: 稳定

选择排序(升序为例)

思路:
1. 选择从第一个到倒数第二个与最后一个进行比较,大则交换放到最后
2. 重复第一步,与倒数第二个数比较

class SelectionSort {
    var array = [5, 7, 2, 8, 9, 4, 7, 3, 2]
    
    func sort() {
        for end in (1 ..< array.count).reversed() {
            var maxValueIndex = 0
            for begin in 1 ... end {
                if array[maxValueIndex] < array[begin] {
                    maxValueIndex = begin
                }
            }
            let tmp = array[maxValueIndex]
            array[maxValueIndex] = array[end]
            array[end] = tmp
        }
    }
}

* 最好、最坏、平均时间复杂度:O(n^2)

* 空间复杂度: O(1)

* 稳定性: 不稳定

相关推荐