文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2022-12-08 20:57

关注

冒泡排序

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

图片演示

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

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

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

普通的冒泡排序算法

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]

小结

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

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

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯