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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法-冒泡、选择排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1684字，纯文字阅读大概需要3分钟。

内容图文

冒泡排序（升序为例）

思路：
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)

* 稳定性： 不稳定

内容总结

以上是互联网集市为您收集整理的排序算法-冒泡、选择排序全部内容，希望文章能够帮你解决排序算法-冒泡、选择排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---