排序算法冒泡排序

冒泡排序（Bubble BubbleSort）
是一种交换排序，他的基本思路是： 两两比较相邻记录的关键字，如果反序则交换。
时间复杂度：
1）最好情况：本身有序，需要比较n-1次 时间复杂度为o(n)
2）最坏情况：逆序情况，需要比较（n-1）+(n-2)+…+2+1=n(n-1)/2 时间复杂度为o（n²）
每一轮的排序对下一轮的排序有帮助，数字如同气泡慢慢往上浮

Paste_Image.png

static void bubbleSort(int[] array) {  
       if (array != null && array.length > 0) {  
           int i, j;  
           for (i = 0; i < array.length; i++) {  
               for (j = array.length - 1; j > i; j--) {  
                   if (array[j] < array[j - 1]) {  
                       swap(array, j, j - 1);  
                   }  
               }  
           }  
       }  
   }```

/**
* 将数组的2个位置交换
*/
static void swap(int[] array, int i, int j) {
if (array != null && array.length > 0) {
if (i >= 0 && j >= 0 && i <= array.length && j <= array.length) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}```
冒泡排序优化(增加tag)，极端情况{2,1,3,4,5,6,7,8,9}后续不用交换

static void bubbleSortTag(int[] array) {  
       if (array != null && array.length > 0) {  
           int i, j;  
           boolean tag = true;//每一轮有木有交换数据  
           for (i = 0; i < array.length && tag; i++) {  
               tag = false;  
               for (j = array.length - 1; j > i; j--) {  
                   if (array[j] < array[j - 1]) {  
                       swap(array, j, j - 1);  
                       tag = true;  
                   }  
               }  
           }  
       }  
   }```