冒泡排序 Bubble Sort

冒泡排序为稳定排序
稳定性：不会改变相同元素的相对顺序。

算法步骤：比较相邻的元素。如果第一个比第二个大，就交换。每轮比较交换完的最后一个数为该轮的最大值以及不参与之后的比较。

时间复杂度：O( n^2 )
当有4个元素，需要比较 3 + 2 + 1 次。
故 n 个元素，需要 n - 1 趟，共比较 (n-1) + ( n - 2) + … + 2 + 1 次。即为等差数列。

去掉低阶项和常数系数得时间复杂度 O(n^2)。
最好情况：O(n)。序列为升序排序。
最坏情况：O(n^2)。序列为降序排序。

空间复杂度：O( 1 )

因为每一个元素都可以像气泡一样，根据自身大小一点一点向数组的一侧移动。所以叫冒泡排序。

优化
（1）立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。（但对提升性能来说没有太大作用）
（2）有序优化：在进行相邻元素比较时，可以记录下循环中没有发生交换的多个连续索引对（起始索引和结束索引），在下次轮询时直接对有序区间的最大值进行比较。
（3）双向冒泡排序：首先从前往后把最大数移到最后，然后反过来从后往前把最小的一个数移动到数组最前面，这一过程就是第一轮，然后重复这一过程，最终就会把整个数组从小到大排列好。双向冒泡排序要稍微优于传统的冒泡排序，因为双向排序时数组的两头都排序好了，我们只需要处理数组的中间部分即可，而单向即传统的冒泡排序只有尾部的元素是排好序的，这时每轮处理都需要从头一直处理到已经排好序元素的前面一个元素。就本质来说，算法上也没什么优化，只是双向调整而已。

java代码

public void bubbleSort(int[] array) {
	for(int i = 0; i < array.length - 1; i ++) {
		for(int j = 0; j < array.length - 1 - i; j ++) {
			if(array[j] > array[j + 1]) {
				int temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
}

public static int[] bubbleSort(int[] arr) {
     if (arr == null || arr.length < 2) { //先判断元素个数是否为0或1
          return arr;
     }
    for (int i = 0; i < arr.length - 1; i++) {
         boolean isSorted  = true;
         for (int j = 0; j < arr.length -i - 1; j++) {
             if (arr[j + 1] < arr[j]) {
                 isSorted  = false;
                 int t = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = t;
             }
         }
         if(isSorted)
              break;
     }
     return arr;
}

public static int[] bubbleSort(int[] arr) {
     if (arr == null || arr.length < 2) {
          return arr;
     }
    int lastExchangeIndex = 0;
    int sortBorder = arr.length - 1;
    
    for (int i = 0; i < arr.length - 1; i++) {
         boolean isSorted  = true;
         for (int j = 0; j < sortBorder; j++) {
             if (arr[j + 1] < arr[j]) {
                 isSorted  = false;
                 int t = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = t;
                 lastExchangeIndex = j;
             }
         }
        sortBorder = lastExchangeIndex
         if(isSorted )
              break;
     }
     return arr;
}