跟着动画学Go数据结构之冒泡排序
【摘要】 冒泡排序冒泡排序是一种最简单的交换排序算法。什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。重复执行若干次冒泡排序，最终得到有序序列。冒泡排序的名字来源于：值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。思想给定一个N个元素的数组，冒泡法排序将：如果元素大小关系...
冒泡排序
冒泡排序是一种最简单的交换排序算法。
什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。
重复执行若干次冒泡排序，最终得到有序序列。
冒泡排序的名字来源于：值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。
思想
- 给定一个N个元素的数组，冒泡法排序将：
如果元素大小关系不正确，交换这两个数（在本例中为a> b），
- 比较一对相邻元素（a，b），
- 重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
- 到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。
动画演示
给定一个数组 29, 10, 14, 37, 14, 48, 17 ，经过冒泡排序的动画如下所示：
代码实现
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
}
}总结
想对比其他排序算法的优点是，它能够检测输入序列是否已经是排序的。
冒泡排序的时间复杂度为
（即使在最好的情况下），空间复杂度为
.
冒泡排序同时也是稳定的算法。
希望本文能对你有所帮助，如果喜欢本文，可以点个赞或者关注，十分感谢！
这里是宇宙之一粟，下一篇文章见！
宇宙古今无有穷期，一生不过须臾，当思奋争。
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）