广告
返回顶部
首页 > 资讯 > 后端开发 > GO >基于Go语言实现冒泡排序算法
  • 117
分享到

基于Go语言实现冒泡排序算法

Go语言实现冒泡排序算法Go语言冒泡排序Go 冒泡排序 2022-12-08 20:12:11 117人浏览 独家记忆
摘要

目录冒泡排序图片演示普通的冒泡排序算法优化算法小结冒泡排序 冒泡排序是交换排序中最简单的一种算法。 算法思路: 遍历数组,相邻的两个元素进行比较,以升序为例,如果前面的元素大于后面的

冒泡排序

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

  • 遍历数组,相邻的两个元素进行比较,以升序为例,如果前面的元素大于后面的元素,则将它们的位置进行交换
  • 第一轮遍历结束之后,最大的元素会处于所遍历范围的最后一个位置,然后继续下一轮遍历
  • 每轮都会固定一个元素,直到所有元素都被固定,因此会执行 n - 1轮,n 为元素的个数,也就是数组(切片)的长度。为什么会是 n - 1 而不是 n,因为到了第 n 轮,只剩下最后一个元素没有被固定,没有元素可以和它进行比较了,因此第 n 轮可以忽略。

图片演示

第一轮遍历 [4, 2, 1, 3]

  • i = 0 时,比较第 i 个元素 4 与第 i + 1 个元素 2 的大小,因为 nums[i] > num[i+1],也就是 4 > 2,因此交换它们的位置。
  • i = 1 时,4 > 1,互换位置。
  • i = 2 时,4 > 3,互换位置。最大值 4 被交换到最后一个位置,此时所有元素都参与比较过了,结束第一轮遍历,执行下一轮遍历。

第二轮遍历 [2, 1, 3, 4]

  • i = 0 时,2 > 1,互换位置。
  • i = 1 时,2 < 3,不做交换。次大值 3 被交换到 4 的左边,此时所有元素都参与比较过了,结束第二轮遍历,执行下一轮遍历。

第三轮遍历 [1, 2, 3, 4]

  • i = 0 时,1 < 2,不做交换。此时所有元素都参与比较过了,结束第三轮遍历,
  • 执行了 n - 1 轮遍历,n 为数组的长度,n - 1个元素被交换到正确的位置,第 n 轮遍历时,只剩最后一个元素,因此不用继续进行。

普通的冒泡排序算法

import "fmt"

func main() {
    nums := [4]int{4, 2, 1, 3}
    fmt.Println("原数组:", nums)
    fmt.Println("--------------------------------")
    NORMalBubbleSort(nums)
}

func NormalBubbleSort(nums [4]int) {
    for i := 0; i < len(nums)-1; i++ {
        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]
            }
        }
        fmt.Printf("第 %d 轮遍历后的数组:%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组:", nums)
}

执行结果:

原数组: [4 2 1 3]
--------------------------------
第 1 轮遍历后的数组:[2 1 3 4]
第 2 轮遍历后的数组:[1 2 3 4]
第 3 轮遍历后的数组:[1 2 3 4]
--------------------------------
排序后的数组: [1 2 3 4]

值得注意的一个地方是第二层循环的条件 j < len(nums)-i-1,为什么会减去 i,因为每轮遍历结束之后,都会有一个元素被固定到后面,因此再进行下一轮的时候,那个元素无须再进行比较。

算法遍历次数为 n -1,每次遍历时元素比较的次数依次为 n - 1、n - 2、n - 3、···、3、2、1,将所有次数求和 = 1 + 2 + 3 + ··· + n - 2 + n - 1= n - 1 * (n - 1 + 1) / 2 = (n² - 1) / 2,因此时间复杂度为 O(n²)。

优化算法

上述例子中,对数组 [4,2,1,3] 进行排序,我们来看看对数组 [4,2,1,3,5] 进行排序,打印数组排序的变化过程中:

原数组: [4 2 1 3 5]
--------------------------------
第 1 轮遍历后的数组:[2 1 3 4 5]
第 2 轮遍历后的数组:[1 2 3 4 5]
第 3 轮遍历后的数组:[1 2 3 4 5]
第 4 轮遍历后的数组:[1 2 3 4 5]
--------------------------------
排序后的数组: [1 2 3 4 5]

不难看出,第三轮与第四轮遍历过程中,都没有进行元素交换位置的操作,对此我们可以推出一个结论,如果在一轮遍历中,没有进行元素交换位置的操作,那么此时数组的里所有元素都处于正确位置。 根据这个结论,我们可以对算法进行优化:

import "fmt"

func main() {
    nums := [5]int{4, 2, 1, 3, 5}
    fmt.Println("原数组:", nums)
    fmt.Println("--------------------------------")
    BestBubbleSort(nums)
}

func BestBubbleSort(nums [5]int) {
    isSwapped := true
    for isSwapped {
        isSwapped = false
        for i := 0; i < len(nums)-1; i++ {
            if nums[i] > nums[i+1] {
                nums[i], nums[i+1] = nums[i+1], nums[i]
                isSwapped = true
            }
        }
        fmt.Println("遍历后的数组:", nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组:", nums)
}

执行结果:

原数组: 
--------------------------------
遍历后的数组: [2 1 3 4 5]
遍历后的数组: [1 2 3 4 5]
遍历后的数组: [1 2 3 4 5]
--------------------------------
排序后的数组: [1 2 3 4 5]

  • 定义交换的标记变量 isSwapper,作为第一层循环的条件,每轮遍历开始之后,将标记变量 isSwapper 赋值为 false,如果在比较的过程中发生元素交换,则将标记变量 isSwapper 赋值为 true。直到 isSwapperfalse 时,数组的里所有元素都处于正确的位置,此时可以结束遍历了。
  • 根据执行结果可知,相比普通的算法,优化后的算法少了一轮遍历,这只是在数组元素少的情况下,如果在数组元素多的情况下,对比结果会更明显。
  • 如果数组为 [5,1,2,3,4],那么算法只会遍历一轮,就能得到正确的排序结果。因此优化后的算法,最好的情况下时间复杂度为 O(N),最坏的情况下仍为 O(N²)。

小结

本文首先对冒泡排序进行简单的介绍,然后通过图片演示冒泡排序的思路。普通冒泡排序算法一共要遍历 n - 1 轮,由测试用例 [4 2 1 3 5] 的结果可以推断出 如果在一轮遍历中,没有进行元素交换位置的操作,那么此时数组的里所有元素都处于正确位置。 根据这个结论,对算法进行优化,优化后的算法,最好的情况下时间复杂度为 O(N)。

到此这篇关于基于Go语言实现冒泡排序算法的文章就介绍到这了,更多相关Go语言冒泡排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

您可能感兴趣的文档:

--结束END--

本文标题: 基于Go语言实现冒泡排序算法

本文链接: https://www.lsjlt.com/news/174508.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • 基于Go语言实现冒泡排序算法
    目录冒泡排序图片演示普通的冒泡排序算法优化算法小结冒泡排序 冒泡排序是交换排序中最简单的一种算法。 算法思路: 遍历数组,相邻的两个元素进行比较,以升序为例,如果前面的元素大于后面的...
    99+
    2022-12-08
    Go语言实现冒泡排序算法 Go语言冒泡排序 Go 冒泡排序
  • go实现冒泡排序算法
    目录1、基本思想2、算法步骤第一轮开始排序: 第二轮开始排序: 第三轮开始排序: 第四轮开始排序: 3、算法实现1、基本思想 通过对待排序序列...
    99+
    2022-11-13
    go 冒泡排序
  • C语言中冒泡排序算法详解
    目录一、算法描述二、算法分析三、完整代码总结一、算法描述 比较相邻两个元素,如果第一个比第二个大则交换两个值。遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面。假设数组有 ...
    99+
    2022-11-12
    C语言冒泡排序法详解 C++冒泡排序算法
  • 如何使用go实现冒泡排序算法
    这篇文章给大家分享的是有关如何使用go实现冒泡排序算法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。1、基本思想通过对待排序序列从后向前,依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素从后部移向前...
    99+
    2023-06-29
  • java实现冒泡排序算法
    介绍冒泡排序是一种算法,比较相邻元素,如果他们处在错误的位置上,那么交换他们的位置。排序可以进行升序或者降序。原理从第一个元素开始,比较第一个元素和第二个元素,如果第一个元素大于第二个元素,那么交换他们的位置。比较 第二个元素和第三个元素的...
    99+
    2018-06-06
    java 冒泡排序 算法
  • Python3 基本排序算法之冒泡排序,
      基本排序算法按时间复杂度分类  O(n^2)  冒泡排序  插入排序  选择排序  Q(n log n)  分而治之  快速排序  归并排序  冒泡排序  相邻的两个元素对比,大的数后推,遍历整个列表一次后,将最大项以冒泡的方式排列i到...
    99+
    2023-01-31
    算法
  • C语言实现冒泡排序算法的示例详解
    目录1. 问题描述2. 问题分析3. 算法设计动图演示4. 程序设计设计一设计二结论5. 流程框架6. 代码实现7. 问题拓展1. 问题描述 对N个整数(数据由键盘输入)进行升序排列...
    99+
    2022-11-13
    C语言 冒泡排序算法 C语言 冒泡排序
  • C语言实现冒泡排序算法代码怎么写
    这篇文章主要介绍“C语言实现冒泡排序算法代码怎么写”,在日常操作中,相信很多人在C语言实现冒泡排序算法代码怎么写问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C语言实现冒泡排序算法代码怎么写”的疑惑有所帮助!...
    99+
    2023-06-29
  • C语言冒泡排序算法代码详解
    今天我们来用C语言实现一下冒泡排序 首先我们来了解一下什么叫做冒泡排序,冒泡顾名思义把质量轻的气体(如二氧化碳一样)浮到水面上(如可乐中的二氧化碳),因此冒泡排序的原理就是N个元素在...
    99+
    2022-11-13
    C语言冒泡排序算法详解
  • 【C语言】用冒泡排序实现my_qsort
    大家好,我是苏貝,本篇博客带大家了解如何用冒泡排序实现my_qsort,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 目录 一. 前言二. 冒泡排序三. ...
    99+
    2023-10-07
    c语言 排序算法 开发语言
  • C语言详解冒泡排序实现
    目录前言一、冒泡排序是什么二、具体步骤1.代码解释2.读入数据总结前言 在排序中,有各种各样的排序方式,今天我们将要来介绍《冒泡排序》。今天会从冒泡排序的具体意义和他的操作来展开。 ...
    99+
    2022-11-13
    C语言 冒泡排序 C语言 排序
  • c语言冒泡排序怎么实现
    C语言冒泡排序的实现步骤如下:1. 定义一个数组来存储待排序的元素。2. 使用两层循环来比较相邻两个元素的大小,并进行交换。3. 外...
    99+
    2023-08-25
    c语言
  • php怎么实现冒泡排序算法
    本文操作环境:windows10系统、php 7、thinkpad t480电脑。在给出具体的实现代码之前,我们先来简单介绍下冒泡排序。冒泡排序是一种比较简单的排序算法,它重复地走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序(...
    99+
    2017-10-26
    php 冒泡排序
  • JS如何实现冒泡排序算法
    这篇文章主要介绍了JS如何实现冒泡排序算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。1. 算法步骤比较相邻的元素。如果第一个比第二个大,...
    99+
    2022-10-19
    js 冒泡排序
  • Python冒泡排序算法怎么实现
    今天小编给大家分享一下Python冒泡排序算法怎么实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。1. 算法描述冒泡排序(...
    99+
    2023-07-02
  • C#实现冒泡排序和插入排序算法
    1.选择排序(冒泡排序) 升序 用第一个元素跟其他元素比较,如果该元素比其他元素,则交换,保证该元素是最小的。然后再用第二个元素跟后面其他的比较,保证第二个元素是除第一个最小的。依次...
    99+
    2022-11-13
    C# 冒泡排序 插入排序
  • 基于Go语言实现选择排序算法及优化
    目录选择排序图片演示普通算法优化算法小结选择排序 选择排序是一种简单的比较排序算法,它的算法思路是首先从数组中寻找最小(大)的元素,然后放到数组中的第一位,接下来继续从未排序的元素中...
    99+
    2022-12-09
    Go语言实现选择排序算法 Go语言选择排序 Go 选择排序
  • C语言实现交换排序算法(冒泡,快速排序)的示例代码
    目录前言一、冒泡排序1.基本思想2.优化3.扩展二、快速排序1.基本思想2.优化3.代码前言 查找和排序是数据结构与算法中不可或缺的一环,是前辈们在算法道路上留下的重要且方便的一些技...
    99+
    2022-11-13
    C语言 交换排序算法 C语言 冒泡排序 C语言 快速排序
  • C语言常见排序算法之交换排序(冒泡排序,快速排序)
    目录前言1.交换排序——冒泡排序1.1 算法思想1.2 动图演示1.3 冒泡最好的情况 2. 交换排序——快速排序...
    99+
    2022-11-13
    C语言常见排序算法 C语言交换排序 C语言冒泡排序 C语言快速排序
  • C#怎么实现冒泡排序和插入排序算法
    这篇文章主要讲解了“C#怎么实现冒泡排序和插入排序算法”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C#怎么实现冒泡排序和插入排序算法”吧!1.选择排序(冒泡排序)升序用第一个元素跟其他元素...
    99+
    2023-06-30
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作