扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 宝典简介

    • 数据结构和算法(Golang实现)
    • 前言
  • 简单入门Golang

  • 基础知识

  • 常见数据结构

  • 排序算法

    • 排序算法
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 优先队列及堆排序
    • 快速排序
  • 查找算法

  • 参考

扫码订阅《 》或入驻星球,即可阅读文章!

冒泡排序


hunterhug

冒泡排序是大多数人学的第一种排序算法,在面试中,也是问的最多的一种,有时候还要求手写排序代码,因为比较简单。

冒泡排序属于交换类的排序算法。

# 一、算法介绍

现在有一堆乱序的数,比如:5 9 1 6 8 14 6 49 25 4 6 3。

第一轮迭代:从第一个数开始,依次比较相邻的两个数,如果前面一个数比后面一个数大,那么交换位置,直到处理到最后一个数,最后的这个数是最大的。

第二轮迭代:因为最后一个数已经是最大了,现在重复第一轮迭代的操作,但是只处理到倒数第二个数。

第三轮迭代:因为最后一个数已经是最大了,最后第二个数是次大的,现在重复第一轮迭代的操作,但是只处理到倒数第三个数。

第N轮迭代:....

经过交换,最后的结果为:1 3 4 5 6 6 6 8 9 14 25 49,我们可以看到已经排好序了。

因为小的元素会慢慢地浮到顶端,很像碳酸饮料的汽泡,会冒上去,所以这就是冒泡排序取名的来源。

举个简单例子,冒泡排序一个 4 个元素的数列:4 2 9 1:

[]表示排好序 {}表示比较后交换的结果

第一轮开始: 4 2 9 1 从第一个数开始,4 比 2 大,交换 4,2
第一轮: {2 4} 9 1  接着 4 比 9 小,不交换
第一轮: 2 {4 9} 1  接着 9 比 1 大,交换 9,1
第一轮: 2 4 {1 9}  已经到底,结束
第一轮结果: 2 4 1 [9] 

第二轮开始:2 4 1 [9] 从第一个数开始,2 比 4 小,不交换
第二轮: {2 4} 1 [9] 接着 4 比 1 大,交换 4,1
第二轮: 2 {1 4} [9] 已经到底,结束
第二轮结果: 2 1 [4 9] 

第三轮开始:2 1 [4 9] 从第一个数开始,2 比 1 大,交换 2,1
第三轮: (1 2} [4 9] 已经到底,结束
第三轮结果: 1 [2 4 9] 

结果: [1 2 4 9]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

首先第一个数 4 和第二个数 2 比较,因为比后面的数大,所以交换,交换后第二个数为 4,然后第二个数 4 和第三个数 9 比较,因为比后面的数小,不交换,接着第三个数 9 和第四个数 1 比较,因为比后面的数大,交换,到达数列底部,第一轮结束。以此类推。

当数列的元素数量为 N,冒泡排序有两种循环,需要比较的次数为:

第一次比较的次数为: N-1 次
第二次比较的次数为: N-2 次,因为排除了最后的元素
第三次比较的次数为: N-3 次,因为排除了后两个元素
...
第某次比较的次数为:  1 次
1
2
3
4
5

比较次数:1 + 2 + 3 + ... + (N-1) = (N^2 - N)/2,是一个平方级别的时间复杂度,我们可以记为:O(n^2)。

交换次数:如果数列在有序的状态下进行冒泡排序,也就是最好情况下,那么交换次数为0,而如果完全乱序,最坏情况下那么交换的次数和比较的次数一样多。

冒泡排序交换和比较的次数相加是一个和 N 有关的平方数,所以冒泡排序的最好和最差时间复杂度都是:O(n^2)。

我们可以改进最好的时间复杂度,使得冒泡排序最好情况的时间复杂度是 O(n),请看下面的算法实现。

冒泡排序算法是稳定的,因为如果两个相邻元素相等,是不会交换的,保证了稳定性的要求。

# 二、算法实现

package main

import "fmt"

func BubbleSort(list []int) {
	n := len(list)
	// 在一轮中有没有交换过
	didSwap := false

	// 进行 N-1 轮迭代
	for i := n - 1; i > 0; i-- {
		// 每次从第一位开始比较,比较到第 i 位就不比较了,因为前一轮该位已经有序了
		for j := 0; j < i; j++ {
			// 如果前面的数比后面的大,那么交换
			if list[j] > list[j+1] {
				list[j], list[j+1] = list[j+1], list[j]
				didSwap = true
			}
		}

		// 如果在一轮中没有交换过,那么已经排好序了,直接返回
		if !didSwap {
			return
		}
	}
}

func main() {
	list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	BubbleSort(list)
	fmt.Println(list)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

输出:

[1 3 4 5 6 6 6 8 9 14 25 49]
1

因为切片会原地排序,排序函数不需要返回任何值,处理完后可以直接打印:fmt.Println(list)。

很多编程语言不允许这样:list[j], list[j+1] = list[j+1], list[j],会要求交换两个值时必须建一个临时变量 a 来作为一个过渡,如:

    a := list[j+1]
    list[j+1] = list[j]
    list[j] = a
1
2
3

但是 Golang 允许我们不那么做,它会默认构建一个临时变量来中转。

我们引入了 didSwap 的变量,如果在一轮中该变量值没有变化,那么表示数列是有序的,所以不需要交换。也就是说在最好的情况下:对已经排好序的数列进行冒泡排序,只需比较 N 次,最好时间复杂度从 O(n^2) 骤减为 O(n)。

# 三、总结

冒泡排序是效率较低的排序算法,可以说是最慢的排序算法了,我们只需知道它是什么,在实际工作上切勿使用如此之慢的排序算法!

赞赏支持

如果你觉得文章不错,请打个赏吧!

  • 一、算法介绍
  • 二、算法实现
  • 三、总结