-
核心思想：比较相邻的两个元素，不符合则交换位置
-
时间复杂度：O(n^2)
-
空间复杂度：O(1)
/**
* 冒泡排序
* 相当于每一次循环都把最大的放到最后面，所以j<array.length- i ，最大的已经在最后了，不需要再循环到它
* 比较相邻的两个元素，不符合则交换位置
* 循环length-1次即可
* 时间复杂度O(n^2)
* 优化策略：
* 1. 使用标志位，如果一次循环都没有进行交换，那么认为已经有序，直接退出
* 2. 使用变量记录最后交换的位置，也就是替换掉j < array.length - 1 - i 为 j< 最后交换的位置。因为每次循环
* 最大的已经放在最后了。其实到最后交换的位置就不需要再往后遍历了
* 3. 冒泡变种优化：鸡尾酒排序，第一轮从左到右，第二轮从右到左，更大的提升效率
* 例子：因为从左到右是把最大的放到后面，如果有个最小值在最后面，其他都是有序的，那么白白移动了其他元素，所以
* 从右到左来一遍，将最小的放在最前。
*/
public static 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]) {
swap(array, j, j + 1);
}
}
}
}