参考
Java排序算法(一)：冒泡排序
特么，谁说的 冒泡排序 很简单
数据结构和算法(Golang实现)(19)排序算法-冒泡排序
问题：假设对数组arr=[9,1,5,8,3,7,4,6,2]由小到大排序
方式一：
从左到右遍历，把每个位置确定下来。
for(i=0;i<len-1;i++){
for(j=i+1;j<len-1;j++){
if(arr[j]>arr[i]){
swap...
执行顺序：
9,1,5,8,3,7,4,6,2//原始顺序
1,9,5,8,3,7,4,6,2//只换一次，就确定第1个位置的数据
1,5,9,8,3,7,4,6,2
1,3,9,8,5,7,4,6,2
1,2,9,8,5,7,4,6,3//交换了三次，但是把3居然交换到最后了，这会导致下一次的循环交换次数增加。所以出现更优化的方式二
方式二：
仍然是从左到右遍历，确定每个位置的数值。但是内部的循环方式不一样，不再和每个数比较，只是和相邻的数比较。参考邻居好说话：冒泡排序
for(i=0;i<len-1;i++){
for(j=len-1;j>=i;j--){//从尾部开始循环
if(arr[j]>arr[j+1]){//把小的往前排，就像冒泡一样
swap...
执行顺序：
9,1,5,8,3,7,4,6,2//原始顺序
9,1,5,8,3,7,4,2,6
9,1,5,8,3,7,2,4,6
9,1,5,8,3,2,7,4,6
9,1,5,8,2,3,7,4,6
9,1,5,2,8,3,7,4,6
9,1,2,5,8,3,7,4,6
1,9,2,5,8,3,7,4,6
继续第二遍循环
1,9,2,5,8,3,4,7,6
1,9,2,5,3,8,4,7,6
1,9,2,3,5,8,4,7,6
1,2,9,3,5,8,4,7,6
/**
* 冒泡排序
*
* @param data
* 目标数组
*/
public static void bubbleSort(int[] data) {
for (int i = 0; i < data.length - 1; i++) {// 控制趟数
for (int j = 0; j < data.length - i - 1; j++) {
if (data[j] > data[j + 1]) {
int tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
}
可以看出，优化主要集中在减少swap次数。方式一会把一个很小的数扔到最后，导致后续的无效swap次数增多。方式二在循环的过程中，一直把小的数字往前调整，直到调整不动为止。可以看出，swap都是有效的。即使前期swap增多，后期swap也会大大减少。
//go version:
func Bubblesort(arrInt []int) (arr []int) {
length := len(arrInt)
//fmt.Println(arrInt)
for i := 0; i < length; i++ {
for j := 0; j < length-1-i; j++ {
if arrInt[j] > arrInt[j+1] {
arrInt[j], arrInt[j+1] = arrInt[j+1], arrInt[j]
}
}
}
return arrInt
//fmt.Println(arrInt)
}
方式二的进一步优化：
假如数组排序前就是2,1,3,4,5,6,7,8,9呢，这样第一次交换后，就已经排好序，后面的比较都浪费了。怎么才能让程序知道已经排好序了呢，答案就是冒泡时发现一个泡都冒不动了。
boolean flag = true;
for(i=0;(i<len-1)&&flag;i++){//
flag = false;
for(j=len-1;j>=i;j--){//从尾部开始循环
if(arr[j]>arr[j+1]){//把小的往前排，就像冒泡一样
flag = true;
swap
可以看出，假如没有swap，flag就会变成false导致循环立即退出。
[时间复杂度]
时间复杂度：最好情况就是排序列表本身有序，此时需要进行n-1次比较，复杂度为O(n)。最坏情况就是完全逆序，需要进行1+2+3+...+(n-1)=n*(n-1)/2,复杂度为O(n^2)。
一般情况下不会使用冒泡排序算法，因为它的比较次数和移动次数和其他排序算法相比，都是最多的，它的唯一好处是算法简单，便于理解。
所以在数据量很小的时候可以使用。
