跟着动画学Go数据结构之冒泡排序 #私藏项目实操分享#

简介: 跟着动画学Go数据结构之冒泡排序 #私藏项目实操分享#

冒泡排序

冒泡排序是一种最简单的交换排序算法。

什么是交换?交换就是两两进行比较,如果不满足次序就可以交换位置。比如,我们想要从小到大排序,通过两个位置上的值两两比较,如果逆序就交换,使关键字大的记录像泡泡一样冒出来放在末尾。

重复执行若干次冒泡排序,最终得到有序序列。

冒泡排序的名字来源于:值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。

思想

  1. 给定一个N个元素的数组,冒泡法排序将:

如果元素大小关系不正确,交换这两个数(在本例中为a> b),

  1. 比较一对相邻元素(a,b),
  2. 重复步骤1和2,直到我们到达数组的末尾(最后一对是第(N-2)和(N-1)项,因为我们的数组从零开始)
  3. 到目前为止,最大的元素将在最后的位置。 然后我们将N减少1,并重复步骤1,直到N = 1。

动画演示

给定一个数组 29, 10, 14, 37, 14, 48, 17 ,经过冒泡排序的动画如下所示:

1.gif

代码实现

package main
import "fmt"
func main() {
    // index starts from 0
    var nums = []int{29, 10, 14, 37, 14, 48, 17}
    var length = len(nums)
    fmt.Println("原数组:", nums)
    bubbleSort(nums, length)
    fmt.Print("数组排序后:")
    for i := 0; i < length; i++ {
        fmt.Printf("%d\t", nums[i])
    }
}
func bubbleSort(nums []int, length int) {
    for i := 0; i < length-1; i++ {
        for j := 0; j < length-i-1; j++ {
            if nums[j] > nums[j+1] { // 如果大,交换
                var temp = nums[j] // 临时变量保存前一个值
                nums[j] = nums[j+1]
                nums[j+1] = temp
            }
        }
    }
}

运行上述代码,可以看到排序的结果:

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\冒泡排序\main.go"
原数组: [29 10 14 37 14 48 17]
数组排序后:10    14  14  17  29  37  48

冒泡排序的优化

可以附加一个标志来改进该算法,在排序过程中,如果没有交换操作意味着排序完成。如果序列已经是有序的,则可以通过判断该标记来结束算法。

func bubbleSortImproved(nums []int, length int) {
    swapped := true
    for i := 0; i < length-1; i++ {
        for j := 0; j < length-i-1; j++ {
            if nums[j] > nums[j+1] {    // 如果大,交换
                var temp = nums[j]      // 临时变量保存前一个值
                nums[j] = nums[j+1]
                nums[j+1] = temp
                swapped = false         //如果没有出现这步骤,说明没有需要交换的了
            }
        }
        if swapped {    // 从头到尾都没有进行交换,说明已经排序完成
            break
        }
    }
}

在最好情况下,改进的冒泡算法的时间复杂度为

网络异常,图片无法展示
|
.

优化二,记录发生交换的位置

func BubbleBestSort(a []int) {
    lastSwap := len(a) - 1
    lastSwapTemp := len(a) - 1
    for j := 0; j < len(a)-1; j++ {
        lastSwap = lastSwapTemp
        for i := 0; i < lastSwap; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i]
                lastSwapTemp = i
            }
        }
        if lastSwap == lastSwapTemp {
            break
        }
    }

总结

想对比其他排序算法的优点是,它能够检测输入序列是否已经是排序的。

image.png

相关文章
|
3月前
|
存储 Go 容器
深入探究Go语言中的数据结构
深入探究Go语言中的数据结构
69 3
|
6天前
|
存储 安全 Go
Go语言中的map数据结构是如何实现的?
Go 语言中的 `map` 是基于哈希表实现的键值对数据结构,支持快速查找、插入和删除操作。其原理涉及哈希函数、桶(Bucket)、动态扩容和哈希冲突处理等关键机制,平均时间复杂度为 O(1)。为了确保线程安全,Go 提供了 `sync.Map` 类型,通过分段锁实现并发访问的安全性。示例代码展示了如何使用自定义结构体和切片模拟 `map` 功能,以及如何使用 `sync.Map` 进行线程安全的操作。
|
5月前
|
搜索推荐 算法 Go
深入探索堆:Go语言中的高效数据结构
深入探索堆:Go语言中的高效数据结构
|
5月前
|
算法 Go
Go 语言 实现冒泡排序
冒泡排序是大家熟知的经典算法。在Go语言中实现它,关键在于理解其核心思想:通过不断比较并交换相邻元素,让序列中的最大值像泡泡一样“浮”至顶端。每一轮比较都能确定一个最大值的位置。外层循环控制排序轮数,内层循环负责比较与交换。随着每轮排序完成,未排序部分逐渐缩小,直至整个数组有序。以下是Go语言实现示例及说明。
46 1
|
6月前
|
存储 算法 Go
go 高并发下的数据结构是怎样?
**变量的字节大小** - `int`, `int32`, `int64` 分别为8, 4, 8字节;指针也为8字节,均受OS影响。 - 空结构体大小为0字节,内存地址相同(`zerobase`),嵌入非空成员后地址不同。 **字符串底层** - 占用16字节,无论长度。 - 底层为`stringStruct`,含指向字符串的指针与长度。 - `StringHeader`类比`stringStruct`用于反射。 **map底层** - 基于`hmap`,含`buckets`、`B`、`count`等,用于散列与管理。 - `bucket`含`tophash`和`overflow`
|
7月前
|
存储 安全 Java
Go语言入门之路——数据结构
Go语言入门之路——数据结构
138 0
|
25天前
|
存储 监控 算法
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
72 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
|
1月前
|
存储 Go 索引
go语言中数组和切片
go语言中数组和切片
45 7
|
1月前
|
Go 开发工具
百炼-千问模型通过openai接口构建assistant 等 go语言
由于阿里百炼平台通义千问大模型没有完善的go语言兼容openapi示例,并且官方答复assistant是不兼容openapi sdk的。 实际使用中发现是能够支持的,所以自己写了一个demo test示例,给大家做一个参考。