-
核心思想:比较相邻的两个元素,不符合则交换位置
-
时间复杂度: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);
}
}
}
}