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

核心思想 通过相邻元素的两两比较，将较大的元素逐步“冒泡”到数组末尾，每轮排序确定一个最大元素的最终位置。 代码实现 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])的方式。可以这么理解。 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) + …*（等差数列求和）。 交换次数： 每次比较均需要交换，总交换次数也为上式结果。