冒泡排序分步可视化

冒泡排序规则说明：

  1. 从数组的第一个元素开始，依次比较相邻的两个元素
  2. 如果前一个元素大于后一个元素，则交换它们的位置
  3. 对每一对相邻元素重复上述比较和交换操作，直到数组末尾
  4. 完成一轮后，最大的元素会"冒泡"到数组的最后位置
  5. 重复上述过程，每次忽略已经排序好的最后一个元素
  6. 当某一轮没有发生任何交换时，说明数组已经排序完成
准备就绪
// 冒泡排序C++实现
void bubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有交换发生，提前结束
if (!swapped) break;
}
}

冒泡排序时间复杂度分析：

最坏情况时间复杂度：O(n²)

计算方式：

1. 外层循环需要执行n-1次（n为数组长度）

2. 内层循环在最坏情况下每次执行n-i-1次比较（i为外层循环次数）

3. 总比较次数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2

4. 因此时间复杂度为 O(n²)

最好情况时间复杂度：O(n)

当数组已经有序时，只需进行一轮n-1次比较即可确定，无需交换

平均时间复杂度：O(n²)

对于随机排列的数组，平均需要进行约n²/2次比较和n²/4次交换

空间复杂度：O(1)

冒泡排序是原地排序算法，只需要常数级别的额外空间