冒泡排序

冒泡排序

Jathon

2022 年 04 月 18 日

349 次浏览

暂无评论

1297字数

Golang DS&AL

## 实现原理

**冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。**

**光看定义有点抽象，我们用图来演示，假设待排序数字是 4、5、6、3、2、1，第一次排序的流程是这样的：**

![冒泡排序](https://bu.dusays.com/2022/04/01/f3497c121588c.png)

**看这个图的时候要结合定义一起看，否则也比较懵逼，当然如果你去 VisuAlgo 上看动态图的话就更形象了：**[https://visualgo.net/zh/sorting](https://visualgo.net/zh/sorting)

![](https://bu.dusays.com/2022/04/01/f9dd028ac4c53.gif)

**经过 n 次冒泡，最终完成排序（所谓冒泡，以升序来看，就是每次把待排序序列中的最大值插到已排序序列的最前面，这个过程就像冒泡一样）：**

![冒泡排序图示](https://bu.dusays.com/2022/04/01/33c8161e41282.png)

## 示例代码

**重要的是理解冒泡排序的原理，懂了原理就是把这个排序过程翻译成代码而已，以下是 Go 代码实现的冒泡排序：**

```
package main

import "fmt"

func bubbleSort(nums []int) []int {
   if len(nums) <= 1 {
      return nums
   }

// 冒泡排序核心实现代码
   for i := 0; i < len(nums); i++ {
      flag := false
      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]
            flag = true
         }
      }
      if !flag {
         break
      }
   }

return nums
}

func main() {
   nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
   nums = bubbleSort(nums)
   fmt.Println(nums)
}
```

**这里我们使用切片类型来存储待排序数据序列，并且可以看到，我们对冒泡排序有个小小的优化，就是当某一次遍历的时候发现没有需要交换的元素，则认为整个序列已经排序完成。**

## 性能分析

**最后我们来看下冒泡排序的性能和稳定性：**

1. **时间复杂度： O(n2)**
2. **空间复杂度：只涉及相邻元素的交换，是原地排序算法**
3. **算法稳定性：元素相等不会交换，是稳定的排序算法**

**时间复杂度是 O(n2)，看起来性能并不是很好，所以我们在实践中基本不会选用冒泡算法。**

最后修改：2022 年 04 月 21 日