冒泡排序(bubble sort)

10大排序算法.png

冒泡排序也叫起泡排序，一般用于对无序数组进行排序；同时冒泡算法属于稳定排序，也具备原地算法特征

假设给定一个无序数组 [1,3,2,5,4,30,10,44,67,33], 请你输出一个升序数组
执行流程：

1. 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置；如此执行完一轮后 最末尾的那个就是最大的元素
   2.忽略1中曾经找到的最大元素，重复执行步骤1的操作，直到全部元素都有序

代码表示

int[] list = {1,3,2,5,4,30,10,44,67,33};
int length = list.length - 1;

//end只需要大于0即可，因为剩下最后一个不需要再比
for(int end = length; end > 0;end--) {
   //begin等于1是因为要跟begin-1对比
    for(int begin = 1;begin <= end;begin++) {
        if(list[begin] < list[begin-1] ) {
           //交换
           int tmp = list[begin];
           list[begin] = list[begin-1];
           list[begin-1] = tmp;
       }
    }
}

优化方案1：其实只要在某一趟扫描完发现没有需要交换的元素了，就可以结束循环了

int[] list = {1,3,2,5,4,30,10,44,67,33};
int length = list.length - 1;

//end只需要大于0即可，因为剩下最后一个不需要再比
for(int end = length; end > 0;end--) {
   boolean sorted = true;
   //begin等于1是因为要跟begin-1对比
    for(int begin = 1;begin <= end;begin++) {
        if(list[begin] < list[begin-1] ) {
           //交换
           int tmp = list[begin];
           list[begin] = list[begin-1];
           list[begin-1] = tmp;
           sorted = false;
       }
    }
  //已经有序就跳出循环
  if(sorted) break;
}

优化方案2：因为一轮循环结束后出现完全排好序的概率并不高，但如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少比较次数

最坏平均时间复杂度: O(n^2)
最好时间复杂度:O(n)
空间复杂度:O(1)

int[] list = {1,3,2,5,4,30,10,44,67,33};
int length = list.length - 1;

//end只需要大于0即可，因为剩下最后一个不需要再比
for(int end = length; end > 0;end--) {

   int sortedIdx = 1;//sortedIdx的初始值在数组完全有序的时候有用
   //begin等于1是因为要跟begin-1对比
    for(int begin = 1;begin <= end;begin++) {
        if(list[begin] < list[begin-1] ) {
           //交换
           int tmp = list[begin];
           list[begin] = list[begin-1];
           list[begin-1] = tmp;
           sortedIdx = begin;
       }
    }
  //一轮结束后就更新，使end保持最后无序的位置
  end = sortedIdx;
}