【数据结构与算法】冒泡排序

核心思想

通过相邻元素的两两比较，将较大的元素逐步“冒泡”到数组末尾，每轮排序确定一个最大元素的最终位置。

代码实现

void bubble_sort(int arr[], int n) {
  // 最外层控制循环轮数 n-1轮
  for (int i = 0; i < n - 1; i++) {
    // 内层循环处理相邻元素比较和交换
    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;
      }
    }
  }
}

// 调用
void print_array(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d,", arr[i]);
  }
  printf("\n");
}

int main() {
  int arr[] = {23, 232, 55, 2, 7, 0, 576, 342};
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("排序前：");
  print_array(arr, n);
  bubble_sort(arr, n);

  printf("排序后");
  print_array(arr, n);
}

原理分析

外层循环的 i < n - 1

n个元素的数组最多需要n-1轮冒泡，如5元素数组需要4轮排序
数学依据：每轮将一个最大值“沉底”，当完成n-1轮时，最后一个元素必然有序

示例验证：

1
2
3

原始数组：[3, 1, 4, 2]
第一轮：[1, 3, 2, 4] （确定最大值4）
第二轮：[1, 2, 3, 4]

用文字解释上面的函数，原理就是在循环中对比数组第i个元素和i+1（即后一位）元素的大小，若i > i +1 则把两者交换位置，随着循环的进行，数组就会被排序。

内层循环的 j < n - i - 1

动态缩小范围：每轮结束后末尾i个元素已有序
比较次数：第i轮需要比较(n-1)-i次相邻元素

想象一下数组的线性结构，实际上就是在计算排序后的一位的前一位，这样就不会处理已经排序好的元素，进入下一轮循环时可正常排序。

数组长度n的计算机制

在main函数中，对于n的计算，采用了sizeof(arr) / sizeof(arr[0])的方式。可以这么理解。

int arr[] = {6,4,8,2};
假设int占用4字节，计算整个数组的内存占用
sizeof(arr) = 5 * 4 = 20
sizeof(arr[0]) = 4
n = 20 / 4 = 5

计算出数组的总占用，再除以单个占用，就可以得到元素个数了。

参数n的作用

循环控制：确定外层循环次数n-1次
边界保护，防止越界
效率优化：避免无效比较，如j<n-i-1

最坏情况

冒泡排序的最坏情况发生在输入数组完全逆序情况下，此时算法需要进行最大次数的比较和交换操作，时间复杂度达到最高。

当待排序数组的初始状态为完全逆序，如[5,4,3,2,1]，每一轮外层循环都要将当前为排序部分的最大元素冒泡到正确位置，而且每次比较都会发生交换，此时：

比较次数：共需要进行*(n - 1) + (n - 2) + …*（等差数列求和）。
交换次数：每次比较均需要交换，总交换次数也为上式结果。