跳转至

HB5-冒泡排序

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 交换两个整数的值
 */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * 带提前终止的冒泡排序（从后往前）
 * 时间复杂度：最好O(n)，最坏O(n²)，平均O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
void bubbleSort(int arr[], int n) {
    // 外层循环控制排序轮数
    for (int i = 0; i < n - 1; i++) {
       int swapped = 0; // 每轮开始前重置标记

        // 内层循环从后往前，将最小元素"冒泡"到前面
        // 范围：从n-1到i+1，因为前面i个位置已经排好序
        for (int j = n - 1; j > i; j--) {
            // 如果前面的元素大于后面的元素，则交换
            if (arr[j - 1] > arr[j]) {
                swap(&arr[j - 1], &arr[j]);
                swapped = 1; // 发生交换，标记置1
            }
        }

        // 如果本轮没有发生任何交换，说明数组已经有序，可以提前终止
        if (swapped == 0) {
            break;
        }
    }
}

✅ 背诵要点总结（口诀式）：

  1. 外层 n-1 趟：for(i=0; i<n-1; i++)
  2. 内层减 i 跑：for(j=0; j<n-i-1; j++)
  3. 前后比较大换后：if(arr[j] > arr[j+1])
  4. 三步交换记心中：temp = a; a = b; b = temp;
  5. 优化加 flag：swapped=0 和 if(swapped==0) break;
  6. 打印看结果：写个 printArray 更直观

📌 算法特点：

  • 时间复杂度：最好 O(n)（已有序），最坏 O(n²)
  • 空间复杂度：O(1)
  • 稳定排序：相同元素相对位置不变