跟着动画学 Go 数据结构之冒泡排序

作者：宇宙之一粟

2021 年 12 月 18 日
本文字数：1790 字
阅读完需：约 6 分钟

冒泡排序

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

什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。

重复执行若干次冒泡排序，最终得到有序序列。

冒泡排序的名字来源于：值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。

思想

给定一个 $N$ 个元素的数组，冒泡法排序将：

如果元素大小关系不正确，交换这两个数（在本例中为 a > b），

比较一对相邻元素（a，b），
重复步骤 1 和 2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
到目前为止，最大的元素将在最后的位置。然后我们将 N 减少 1，并重复步骤 1，直到 N = 1。

动画演示

给定一个数组 29, 10, 14, 37, 14, 48, 17 ，经过冒泡排序的动画如下所示：

代码实现

package mainimport "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        }    }}

复制代码

在最好情况下，改进的冒泡算法的时间复杂度为 $O (n)$ 。

冒泡排序优化二：记录发生交换的位置

其实冒泡算法还有第二种优化方式，如果有 10 个数的数组，仅前面 5 个无序，后面 5 个都已排好序且都大于前面 5 个数字，那么在第一趟遍历后，最后发生交换的位置必定小于 5 ，且这个位置之后的数据必定已经有序了。

改进思路：

记录某次遍历时最后发生数据交换的位置 lastSwap ，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。由于 lastSwap 位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到 lastSwap 位置即可。

读者可以动手试试跑一下如下的代码：

func BubbleBestSort(nums []int, length int) {
    lastSwap := length - 1    lastSwapTemp := length - 1    for j := 0; j < length; j++ {        lastSwap = lastSwapTemp        for i := 0; i < lastSwap; i++ {            if nums[i] > nums[i+1] {                nums[i], nums[i+1] = nums[i+1], nums[i]                lastSwapTemp = i            }        }
        if lastSwap == lastSwapTemp {            break        }    }}

复制代码

总结

冒泡排队相对比其他排序算法的优点是，它能够检测输入序列是否已经是排序的。但是数据量大的冒泡排序的性能就较差了，敬请期待其他的算法。

时间复杂度：冒泡排序的时间复杂度为 $O (n^{2})$ (即使在最好的情况)

空间复杂度：空间复杂度为 $O (1)$ 。

稳定性：冒泡排序同时是稳定的算法。

发布于: 4 小时前阅读数: 5

原文链接:【http://xie.infoq.cn/article/5398fc949b90c60a80631b4ff】。文章转载请联系作者。

宇宙之一粟

关注

宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入

混迹于江湖，江湖却没有我的影子热爱技术，专注于后端全栈，轻易不换岗拒绝内卷，工作于软件工程师，弹性不加班热衷分享，执着于阅读写作，佛系不水文各大平台同名 CSDN、51CTO、掘金、知乎、公众号、简书。。。

发布

暂无评论

创作场景

跟着动画学 Go 数据结构之冒泡排序

冒泡排序

思想

动画演示

代码实现

冒泡排序的优化一

冒泡排序优化二：记录发生交换的位置

总结

宇宙之一粟

评论