核心思想

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

代码实现

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轮时，最后一个元素必然有序

示例验证：

……

Continue reading