Go 数据结构和算法篇(四):冒泡排序

Go语言精选

共 2616字,需浏览 6分钟

 ·

2021-04-18 22:03

今天给大家介绍的是基于选择的排序算法,常见基于选择的排序算法有冒泡排序、插入排序、选择排序、归并排序和快速排序,我们在选择排序算法的时候,通常会根据以下几个维度来考虑:

  1. 时间复杂度

  2. 空间复杂度(对内存空间的消耗)

  3. 算法的稳定性(如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变)

我们首先从冒泡排序开始。

实现原理

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

光看定义有点抽象,我们用图来演示,假设待排序数字是 4、5、6、3、2、1,第一次排序的流程是这样的:

冒泡排序

看这个图的时候要结合定义一起看,否则也比较懵逼,当然如果你去 VisuAlgo 上看动态图的话就更形象了:https://visualgo.net/zh/sorting,经过 n 次冒泡,最终完成排序(所谓冒泡,以升序来看,就是每次把待排序序列中的最大值插到已排序序列的最前面,这个过程就像冒泡一样):

冒泡排序图示

示例代码

重要的是理解冒泡排序的原理,懂了原理就是把这个排序过程翻译成代码而已,以下是 Go 代码实现的冒泡排序:

package main

import "fmt"

func bubbleSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // 冒泡排序核心实现代码
    for i := 0; i < len(nums); i++ {
        flag := false
        for j := 0; j < len(nums) - i - 1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = true
            }
        }
        if !flag {
            break
        }
    }

    return nums
}

func main() {
    nums := []int{45678321}
    nums = bubbleSort(nums)
    fmt.Println(nums)
}

这里我们使用切片类型来存储待排序数据序列,并且可以看到,我们对冒泡排序有个小小的优化,就是当某一次遍历的时候发现没有需要交换的元素,则认为整个序列已经排序完成。

性能分析

最后我们来看下冒泡排序的性能和稳定性:

  1. 时间复杂度:O(n2)

  2. 空间复杂度:只涉及相邻元素的交换,是原地排序算法

  3. 算法稳定性:元素相等不会交换,是稳定的排序算法

时间复杂度是 O(n2),看起来性能并不是很好,所以我们在实践中基本不会选用冒泡算法。

(本文完)



推荐阅读


福利

我为大家整理了一份从入门到进阶的Go学习资料礼包,包含学习建议:入门看什么,进阶看什么。关注公众号 「polarisxu」,回复 ebook 获取;还可以回复「进群」,和数万 Gopher 交流学习。

浏览 11
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报