# 什么是冒泡法？
冒泡法是基本排序算法的一种，它是稳定的排序算法，其时间复杂度是O(n^2)
下面引用冒泡法的wiki解释
> 冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
我现在使用go语言来实现一下go版本的一般性的冒泡法：
```go
for i := 0; i < len(arr);i++ {
for j := 0; j < len(arr)-1-i;j++{
if arr[j] > arr[j+1] {
swap(arr,j,j+1)
}
}
}
```
那么这个算法就这么结束了吗？
## 冒泡排序的优化
我们知道冒泡法的基本原理就是不断的比较，当把所有的数据都比较结束后，这个排序才算结束，所以每次内层的for就是一次冒泡的过程，每次都少1，然后直到最后一个数据，这样看来数据是依次减少的。外层是n，内部依次是n n-1 n-2 ....1，所以它实际的执行过程的和是
```bash
n + n-1 + n-2 ...+1
//加在一起就是
n x n - (1+...n)
= (n^2 - n)x0.5
```
那么我们就发现了这个执行的过程是外面n里面也约等于n，一定是n吗？一定要执行n次吗？
如果某一次的冒泡过程全员未动，不就意味着排序结束吗？
## 优化代码实现
```go
for i := 0; i < len(arr); i++ {
f := false
for j := 0;j < len(arr) -1 - i;j++ {
if arr[j] < arr[j+1]{
swap(arr,j,j+1)
f = true
}
}
// 如果某一次执行完毕了还是false，那么就证明这一次压根没有进行交换
// 也就是说已经排序结束了，可以跳出了。
if !f {
break
}
}
```
这个小小的优化如果在数据量大以及前面数据都是顺序的情况下，可以节约非常多的时间。这种小优化在面试的时候也能让面试官眼前一亮，觉得你好牛逼。????
当然也有垃圾面试官，我的就是，他直接质疑我错了，直到1分钟后，他直接要了我。。。emm。。。选择公司要谨慎。。。
## 欢迎添加公众号一起学编程！
有疑问加站长微信联系（非本文作者））
