前言
上一篇：http://www.haodaquan.com/139 介绍了冒泡排序算法的一种优化方法，那就是我们根据冒泡排序的特点，减少了内层循环次数，从而提高了算法的执行速度，那外层循环能否也可以减少一下循环次数呢？
分析
我们假设m个元素需要排序，当我们进行到i次排序的时候，如果发现内层循环的元素都是排好序的，那我们就可以提前结束外层循环。
怎么判断内层循环的元素是排好序呢，很简单，如果内层循环不交换元素位置了，说明排序已经排好了，此时可以提前结束内层循环。
于是，我们有了以下的想法：每次内层循环的时候，设置变量flag=true,即假设内层循环的元素是有序的，然后发现一旦有交换位置的操作，将flag设置为false，我们在内层循环之后判断flag是否为true，如果是，那就可以提前结束外层循环。
代码
我们有了以下的golang代码实现，并且将上一次优化的方法一起结合起来：
func Sort4(arr []int) []int {
len := len(arr)
if len < 2 {
return arr
}
for i := 0; i < len-1; i++ {
flag := true
for j := 0; j < len-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j+1], arr[j] = arr[j], arr[j+1]
flag = false
}
}
if flag {
break
}
}
return arr
}
优缺点
这种算法，对于近乎有序的元素排序，效率是最高的。当然，如果反序的（从大到小排列）的元素排序，因为增加了一个判断，可能效率就不是那么高了。
github代码
下面是代码的实现以及测试代码：
https://github.com/george518/PPGo_algorithm/tree/master/sort/bubble
比较一下，看哪种算法时间最短，是不是和我们理论上的分析是一致，这里我就不贴测试结果了
