--- abbrlink: 403994443 categories: - 往昔 date: "2025-05-10 20:06:05" tags: - 数据结构与算法 title: 【数据结构与算法】冒泡排序 --- ## 核心思想 通过相邻元素的两两比较，将较大的元素逐步“冒泡”到数组末尾，每轮排序确定一个最大元素的最终位置。 ## 代码实现 ```c 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轮时，最后一个元素必然有序 示例验证： ``` 原始数组：[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])`的方式。可以这么理解。 ```c 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