排序算法:冒泡排序,golang实现

目录

前言

冒泡排序

代码示例

1. 算法包

2. 冒泡排序代码

3. 模拟排序

4. 运行程序

5. 从大到小排序

循环细节

外层循环

内层循环

总结

循环次数测试

假如 10 条数据进行排序

假如 20 条数据进行排序

假如 30 条数据进行排序

假设 5000 条数据,对比 选择、插入、快速、堆、归并

冒泡排序的适用场景

1. 数据量非常小

2. 数据几乎有序

3. 教学用途

4. 稳定性


前言

在实际场景中,选择合适的排序算法对于提高程序的效率和性能至关重要,本节课主要讲解"冒泡排序"的适用场景及代码实现。

冒泡排序

冒泡排序(Bubble Sort) 是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢"浮"到数列的顶端。

代码示例

下面我们使用Go语言实现一个冒泡排序:

1. 算法包

创建一个 pkg/algorithm.go 

touch pkg/algorithm.go

2. 冒泡排序代码

打开 pkg/algorithm.go 文件,代码如下

从小到大 排序

package pkg// BubbleSort 冒泡排序
func BubbleSort(arr []int) {n := len(arr)              // 获取切片长度for i := 0; i < n-1; i++ { // 外层循环控制遍历的次数for j := 0; j < n-i-1; j++ { // 内层循环控制每轮遍历的次数,每完成一轮,最大数就“冒泡”到最后if arr[j] > arr[j+1] { // 比较相邻元素,如果前一个比后一个大,则交换arr[j], arr[j+1] = arr[j+1], arr[j] // 两个元素换位置}}}
}

3. 模拟排序

打开 main.go 文件,代码如下:

package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片,这里我们模拟 10 个元素arr := []int{999, 452, 37, 1573, 234, 5, 318, 76483, 115, 86}fmt.Println("Original data:", arr) // 先打印原始数据pkg.BubbleSort(arr)                // 调用冒泡排序fmt.Println("New data:  ", arr)    // 后打印排序后的数据
}

4. 运行程序

打开终端,我们运行 go :

go run main.go

能发现, Original data 后打印的数据,正是我们代码中定义的切片数据,顺序也是一致的。

New Data 后打印的数据,则是经过冒泡排序后的数据,是从小到大的。

5. 从大到小排序

如果需要 从大到小 排序也是可以的,在代码里,将两个元素比较的 大于符号 改成 小于符号 即可。

修改 pkg/algorithm.go 文件:

package pkg// BubbleSort 冒泡排序
func BubbleSort(arr []int) {n := len(arr)              // 获取切片长度for i := 0; i < n-1; i++ { // 外层循环控制遍历的次数for j := 0; j < n-i-1; j++ { // 内层循环控制每轮遍历的次数,每完成一轮,最大数就“冒泡”到最后if arr[j] < arr[j+1] { // 比较相邻元素,如果前一个比后一个大,则交换arr[j], arr[j+1] = arr[j+1], arr[j] // 两个元素换位置}}}
}

只需要一丁点的代码即可

在第八行代码中,我们将 ">" 改成了 "<" ,这样就变成了 从大到小排序了

循环细节

心细的同学已经发现,我们的外层循环中,有 "n - 1",而内层循环中,有 "n - i - 1"

外层循环

外层循环控制的是遍历数组的总轮数。在冒泡排序中,没完成一轮遍历,都会确保至少有一个元素被放置到它最终的位置上。因此,随着排序的进行,未排序的元素数量逐渐减少。

  • 初始时,未排序的元素是整个数组,长度为 n
  • 第一轮遍历后,最大的元素被放到了数组的最后一位,因此未排序的元素减少了一个,剩下 n - 1 个
  • 第二轮遍历后,第二大的元素被放到了倒数第二个,未排序的元素再减少一个,剩下 n - 2 个
  • 以此类推,直到所有的元素都排序完成

因此,外层循环的次数是 n - 1,即

for i := 0; i < n - 1; i ++ {}

内层循环

内层循环负责在每一轮遍历中,通过相邻元素的比较和交换,将未排序部分的最大元素"冒泡"到其正确位置。随着外层循环的进行,每一轮结束后,数组的末尾都会增加一个已排序的元素(即最大元素),因此内层循环的遍历范围需要相应减少。

  • 初始时,内层循环需要遍历整个未排序的数组,即 j 从 0 到 n - 1。但由于每次遍历结束时,最后一个元素都会是未排序部分的最大值,所以实际上内层循环只需要遍历到 n - 2 (因为最后一个元素已经是最大的了,无需再比较)
  • 随着外层循环的进行(即 i 的增加),每一轮结束时,数组的末尾都会增加一个已排序的元素,因此,每进入下一轮外层循环,内层循环的遍历范围就可以减少一个元素,即 n - i - 1

综上,内层循环的条件是

for j := 0; j < n - i - 1; j ++ {}

这里的 n - i - 1 确保了内层循环每次只遍历当前未排序的部分。

总结

外层循环的减 1 是因为每轮排序后,都有一个元素被确定位置,不需要再参与后续的排序;

内层循环的减 1 和减 i 是因为随着排序的进行,未排序的元素数量在逐渐减少,需要相应地调整遍历范围。

循环次数测试

按照上面示例进行测试:

假如 10 条数据进行排序

外层循环了 9

内层循环了 45

总计循环了 54

假如 20 条数据进行排序

外层循环了 19 

内层循环了 190 

总计循环了 209

假如 30 条数据进行排序

外层循环了 29 

内层循环了 435 

总计循环了 464 次

...

会发现,仅仅只是增加了 10 条数据,或者是 20 条数据,循环次数则是成几倍甚至十倍增长,所以数据量稍微多一点,是不建议使用 冒泡排序

假设 5000 条数据,对比 选择、插入、快速、堆、归并

  • 冒泡排序:循环次数 12,502,499 次
  • 选择排序:循环次数 12,502,499 次
  • 插入排序:循环次数 6,323,958 次
  • 快速排序:循环次数 74,236 次
  • 堆排序:循环次数 59,589 次
  • 归并排序:循环次数 60,288 次

冒泡排序的适用场景

尽管冒泡排序在大多数情况下并不是最高效的排序算法(其平均和最坏情况时间复杂度均为 O( n ^ 2),其中 n 是数组的长度),但在某些特定场景下,它仍然有其应用价值

1. 数据量非常小

当需要排序的数据量非常小时,冒泡排序的简单性可能会使其成为一种快速且易于实现的解决方案

2. 数据几乎有序

如果数据已经是接近排序的状态,那么冒泡排序的效率会相对较高,因为它在遍历过程中可以迅速地将大部分元素排序好,从而减少后续遍历的次数

3. 教学用途

由于其算法简单易懂,冒泡排序经常被用作教学算法,帮助学生理解排序算法的基本思想和过程

4. 稳定性

冒泡排序是一种稳定的排序算法,即如果两个相等的元素在排序前的相对顺序和在排序后的相对顺序相同。在某些需要保持元素原始的场合,冒泡排序可能是一个合适的选择

综上所述,虽然冒泡排序在大多数情况下不是最优选择,但在特定场景下,它仍然有其独特的优势和价值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/390862.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

荒原之梦考研:专科考研成功的可能性大吗?

专科还是本科不是决定考研能否成功的关键因素&#xff0c;决定考研能否成功的关键因素是自己是否有清晰的规划、是否有足够的专注能力&#xff0c;以及是否能够吃得了考研的“苦”。 首先要有清晰的规划&#xff0c;比如说&#xff0c;不是我们每个人足够努力就都能考上 TOP1 …

很简单的Win10+Win7双系统教程|UEFI篇

前言 前段时间有写过一篇关于Windows10Windows7双系统安装教程&#xff0c;但这个教程为了比较保险&#xff0c;就进入了WinPE维护系统进行操作。 但有很多小伙伴就有点搞不懂了&#xff0c;都不知道WinPE是什么系统&#xff0c;也不知道怎么去解决这个问题。 今天咱们就来讲…

centos7部署智能dns实战应用

主DNS&#xff1a;192.168.101.129 备DNS&#xff1a;192.168.101.128 原理&#xff1a; 一、下载软件 bind-9.17.9.tar.xz的下载地址&#xff1a;https://ftp.isc.org/isc/bind9/9.17.9/bind-9.17.9.tar.xz。更多的bind版本可以从https://ftp.isc.org/isc/bind9/下载。 二&a…

【深入探秘Hadoop生态系统】全面解析各组件及其实际应用

深入探秘Hadoop生态系统&#xff1a;全面解析各组件及其实际应用 引言 在大数据时代&#xff0c;如何高效处理和存储海量数据成为企业面临的重大挑战。根据Gartner的统计&#xff0c;到2025年&#xff0c;全球数据量将达到175泽字节&#xff08;ZB&#xff09;&#xff0c;传…

学习安卓开发遇到的问题

问题1&#xff1a;学习禁用与恢复按钮中&#xff1a; java代码报错&#xff1a;报错代码是 R.id.btn_enable;case R.id.btn_disable;case R.id.btn_test: 代码如下&#xff1a;&#xff08;实现功能在代码后面&#xff09; package com.example.apptest;import static java.…

【时时三省】unity test 测试框架 介绍(适用于C语言进行测试的)

1&#xff0c;关于 unity test 测试框架的介绍 unity test 是 ThrowTheSwitch.org 的一个主要工程。它是专注于为嵌入式工具链而生的C语言单元测试框架。它可以适用于大工程或者小工程都可以。它的核心文件是一个.c文件和两个头文件。 备注&#xff1a; 下载源码地址&#xff…

应急响应-Web3

打开虚拟机之后&#xff0c;运行解题系统&#xff1a; 共有三个问题&#xff01; 攻击者的两个IP地址 首先我们看到机器的桌面上还是存在phpstudy&#xff0c;那就还是先去看看是不是从web层面进行的攻击&#xff0c;上传webshell从而getshell。 利用D盾尝试对phpstudy目录进…

WordPress资源下载类主题 CeoMax-Pro_v7.6绕授权开心版

CeoMax-Pro强大的功能 在不久的将来Ta能实现你一切幻想&#xff01;我们也在为此而不断努力。适用于资源站、下载站、交易站、素材站、源码站、课程站、cms等等等等&#xff0c;Ta 为追求极致的你而生。多风格多样式多类型多行业多功能 源码下载&#xff1a;ceomax-pro7.6.zip…

【系统架构设计师】二十四、安全架构设计理论与实践②

目录 三、系统安全体系架构规划框架 3.1 信息系统安全体系规划 3.2 信息系统安全规划框架 3.2.1 信息系统安全规划依托企业信息化战略规划 3.2.2 信息系统安全规划需要围绕技术安全、管理安全、组织安全考虑 3.2.3 信息系统安全规划以信息系统与信息资源的安全保护为核心…

[环境配置]Pycharm:Failed to start [PowerShell.exe]

解决方法&#xff0c;点Local旁边的 号&#xff0c;点击Command Prompt&#xff0c;即可在Pycharm中呼出控制台。 如果要修改Command Prompt的启动时访问的cmd.exe的路径&#xff0c;可以去Settings→Tools→Terminal中&#xff0c;修改Shell Path实现&#xff0c;改为cmd.exe…

AWS开发人工智能:如何基于云进行开发人工智能AI

随着人工智能技术的飞速发展&#xff0c;企业对高效、易用的AI服务需求日益增长。Amazon Bedrock是AWS推出的一项创新服务&#xff0c;旨在为企业提供一个简单、安全的平台&#xff0c;以访问和集成先进的基础模型。本文中九河云将详细介绍Amazon Bedrock的功能特点以及其收费方…

117页PPT埃森哲-物流行业信息化整体规划方案

一、埃森哲-物流行业信息化整体规划方案 资料下载方式&#xff0c;请看每张图片右下角信息 埃森哲在物流行业信息化整体规划项目中的核心内容&#xff0c;旨在帮助物流企业通过信息技术的应用实现业务流程的优化、运营效率的提升以及市场竞争力的增强。以下是埃森哲在此类项目…

C语言指针(1)

目录 一、内存和地址 1、生活中的例子 2、内存的关系 二、指针变量和地址 1、&符号&#xff0c;%p占位符 2、一个简单的指针代码。 3、理解指针 4、解引用操作符 5、指针变量的大小。 三、指针变量类型的意义 1、指针解引用的作用 2、指针指针 3、指针-指针 4…

Python初学者必须掌握的基础知识点

Python初学者必须掌握的基础知识点包括数据类型与变量、控制结构&#xff08;条件语句和循环语句&#xff09;、基本数据结构&#xff08;列表、元组、字典、集合&#xff09;、函数与模块、以及字符串处理等。以下是对这些基础知识点及其对应代码的详细介绍&#xff1a; 1. …

利用Llama 3 API实现盈利:细节解析

随着人工智能技术的快速发展,基于大模型的服务成为了众多初创企业关注的焦点。Llama 3 API作为一种强大的语言模型接口,为小型公司提供了利用先进AI技术的机会。本文将探讨这些小公司如何通过Llama 3 API实现盈利,并分析其中的关键因素。 一、Llama 3 API性能概览 批处理输…

Golang | Leetcode Golang题解之第318题最大单词长度乘积

题目&#xff1a; 题解&#xff1a; func maxProduct(words []string) (ans int) {masks : map[int]int{}for _, word : range words {mask : 0for _, ch : range word {mask | 1 << (ch - a)}if len(word) > masks[mask] {masks[mask] len(word)}}for x, lenX : ra…

设计模式 - Singleton pattern 单例模式

文章目录 定义单例模式的实现构成构成UML图 单例模式的六种实现懒汉式-线程不安全懒汉式-线程安全饿汉式-线程安全双重校验锁-线程安全静态内部类实现枚举实现 总结其他设计模式文章&#xff1a;最后 定义 单例模式是一种创建型设计模式&#xff0c;它用来保证一个类只有一个实…

Candance Allegro 入门教程笔记:PCB封装库的组成元素

文章目录 一、PCB封装库的组成元素二、使用Padstack Edictor制作封装焊盘引脚三、PCB Editor软件创建贴片封装&#xff08;STM32F103T8U6 QFN36 为例&#xff09;1.引入库2.读入数据 一、PCB封装库的组成元素 一般来说&#xff0c;针对于Allegro软件&#xff0c;完整的封装是由…

数据结构之《二叉树》(中)

在数据结构之《二叉树》(上)中学习了树的相关概念&#xff0c;还了解的树中的二叉树的顺序结构和链式结构&#xff0c;在本篇中我们将重点学习二叉树中的堆的相关概念与性质&#xff0c;同时试着实现堆中的相关方法&#xff0c;一起加油吧&#xff01; 1.实现顺序结构二叉树 在…

数据结构:带索引的双链表IDL

IDLindexed double list 如图&#xff0c;下方是一个双链表&#xff0c;上方是索引。索引储存为结构体数组&#xff0c;结构体内包括一个指针&#xff0c;和长度。 假设索引只有一个&#xff0c;这时&#xff0c;它应该指向双链表的中间&#xff0c;这样才能提高搜索效率。称…