[冒泡排序 bubble sort] 通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样。
冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果 “左元素> 右元素” 就交换它俩。遍历完成后，最大的元素会被移动到数组的最右端。
冒泡排序算法流程：
- 首先，对 n 个元素执行 ” 冒泡 “，将数组的最大元素交换至正确位置。
- 接下来，对剩余 n-1 个元素执行 ” 冒泡 “，将第二大元素交换至正确位置。
- 以此类推，经过 n-1 轮 ” 冒泡 “ 后，前 n-1 大的元素都被交换至正确位置。
- 仅剩的一个元素必定是最小元素，无需排序，因此数组排序完成。
/* 冒泡排序 */
void BubbleSort(int[] nums) {
// 外循环：未排序区间为 [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
}
}
}
}
效率优化：如果某轮 “冒泡” 中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位 flag 来监测这种情况，一旦出现就立即返回。
/* 冒泡排序（标志优化）*/
void BubbleSortWithFlag(int[] nums) {
// 外循环：未排序区间为 [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
bool flag = false; // 初始化标志位
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
flag = true; // 记录交换元素
}
}
if (!flag) break; // 此轮冒泡未交换任何元素，直接跳出
}
}