前言
上一篇http://www.haodaquan.com/139 我们一起讨论了冒泡算法的第二种优化方式：提前结束外层循环。并且也加上了第一种优化方式，提前结束内层循环，但是，这种算法对于反序排列的元素（如：9，8，7，6，5，4，3，2，1）排序，效率低下。
分析
假设：有一个数组[7,1,2,3,4,6,8,9,10],我们发现，1234与8910其实是排好序的，能不能这两部分不参与循环呢？
问题的关键我们需要找到最后一个不需要排序的索引值（当然，不一定准确的索引值），这个索引值等于内层循环的交换的值中的最大值。
Golang代码
我们结合上一次优化的方法，给出以下golang的排序代码：
func Sort5(arr []int) []int {
len := len(arr)
if len < 2 {
return arr
}
k := len - 1
lastIndex := 0
for i := 0; i < len-1; i++ {
flag := true
for j := 0; j < k; j++ {
if arr[j] > arr[j+1] {
arr[j+1], arr[j] = arr[j], arr[j+1]
flag = false
lastIndex = j
}
}
if flag {
break
}
k = lastIndex
}
return arr
}
优缺点：
这种算法对于近乎有序的元素排序，那是相当的酸爽，算法时间复杂度直接优化成O(1),相反，对于一个反序的元素组排序，算法复杂度会变成O(n^2),并且因为多了判断和赋值，时间会比其他冒泡算法效率会更低。
Github完整代码
下面是代码的实现以及测试代码：
https://github.com/george518/PPGo_algorithm/tree/master/sort/bubble
比较一下，看哪种算法时间最短，是不是和我们理论上的分析是一致，这里我就不贴测试结果了
