核心思想
冒泡排序是基于相邻元素相互比较的排序算法，算法的核心有2点：
- 内外双循环：
- 外循环遍历数组；
- 内循环遍历数组并比较相邻元素大小和互换位置。
- 内循环结束后都会把最大/最小值移动到数组的头部或末尾。
时间复杂度和稳定性
当数组的元素是 n 个 0 到 m 之间的整数时，最坏时间复杂度是O(n)，最好时间复杂度是O(n^2)，空间复杂度是O(1)。
冒泡排序是一个稳定的排序算法。
适用范围
无限制。
Java 实现
注意点
- 排序什么时候完成：
- 使用一个flag来标记内循环是否发生过数据交换，如果没有发生过，表示排序完成。
- 基于“内循环结束后都会把最大/最小值移动到数组的头部或末尾”这一点，尽量减少内循环的循环次数：
- 外循环循环到第i次时，内循环无需比较数组末尾的i个元素。
import java.util.Arrays;
/**
* 冒泡排序
*
* @author Alisallon
* Created on 2021/6/5 2:45 下午.
*/
public class BubbleSort {
public static void main(String[] args) {
int[] nums = {2, 3, 6, 8, 4, 2, 1, 8, 9, 4, 8, 0, 2, 3, 4, 9, 6, 5, 7, -3, -1, -7, -4, -9, -10, -5, -6};
System.out.println(Arrays.toString(sort(nums)));
}
/**
* 冒泡排序实现
*
* @param nums 原数组
* @return 排序后的数组
*/
private static int[] sort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 标记内循环是否发生过数据交换
boolean hadSwap = false;
// 内循环无需比较数组末尾的i个元素
int maxIndex = nums.length - 1 - i;
for (int j = 0; j < maxIndex; j++) {
if (nums[j] > nums[j + 1]) {
// 交换方式1
// int temp = nums[j];
// nums[j] = nums[j + 1];
// nums[j + 1] = temp;
// 交换方式2(三次相同异或计算即可)
nums[j] = nums[j] ^ nums[j + 1];
nums[j + 1] = nums[j] ^ nums[j + 1];
nums[j] = nums[j] ^ nums[j + 1];
// 标记已发生过数据交换
hadSwap = true;
}
}
if (!hadSwap) {
// 没有发生数据交换,排序完成
return nums;
}
}
return nums;
}
}
