冒泡排序：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来
基本思路
冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。
重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。
实现逻辑
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
通过两层循环控制：
- 第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
- 第二个循环（内循环），负责两两比较交换。
动图演示
java
public static void bubbleSort(int[] arr) {
// 如果数组为空或长度小于2，则直接返回，无需排序
if (arr == null || arr.length < 2) return;
// 外层循环，从数组长度减1开始遍历到1，表示每次循环都会将最大的元素冒泡到最后
for (int i = arr.length - 1; i > 0; i--) {
// 内层循环，从第一个元素开始遍历到当前最大元素的前一个位置
// 进行相邻元素的比较和交换
for (int j = 0; j < i; j++) {
// 如果当前元素比后一个元素大，则交换它们的位置
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
// 交换数组中两个元素的位置，使用异或运算实现交换
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
文档信息
- 本文作者：carpe
- 本文链接：https://carpedx.com/wiki/algorithm-bubble-sort/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）