目录

C 语言冒泡排序算法详解

引言

工作原理

示例代码

代码解释

时间复杂度和空间复杂度

---

C 语言冒泡排序算法详解

引言

冒泡排序是一种简单的排序算法，它通过重复地遍历要排序的列表，比较相邻的元素并根据需要交换它们的位置来实现排序。尽管冒泡排序的时间复杂度较高（O(n²)），但它因其简单易懂而常用于教学目的。本文将详细介绍冒泡排序的工作原理，并提供一个用 C 语言实现的示例。

工作原理

冒泡排序的基本思想是通过多次遍历待排序的列表，每次遍历时比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。这样，每遍历一次，最大的元素就会像气泡一样“浮”到列表的末尾。这个过程会重复进行，直到整个列表变得有序。

具体步骤如下：

1. 初始化：设定一个外部循环，控制遍历次数。
2. 内部遍历：设定一个内部循环，用于比较和交换相邻的元素。
3. 比较和交换：在内部循环中，如果前一个元素大于后一个元素，则交换它们的位置。
4. 重复：外部循环每执行一次，最大的未排序元素就会被移动到它最终的位置，内部循环的范围就会减少一个元素。

示例代码

下面是一个用 C 语言实现的冒泡排序示例：

#include <stdio.h>

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        // 最后i个元素已经到位，不需要再比较
        for (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 printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

代码解释

1. 主函数 main：

   • 定义一个整数数组 arr 并初始化。
   • 计算数组的长度 n。
   • 打印原始数组。
   • 调用 bubbleSort 函数对数组进行排序。
   • 打印排序后的数组。

2. 冒泡排序函数 bubbleSort：

   • 使用两个嵌套的 for 循环来遍历数组。
   • 外部循环控制遍历次数。
   • 内部循环用于比较和交换相邻的元素。
   • 如果前一个元素大于后一个元素，则交换它们的位置。

3. 打印数组函数 printArray：

   • 遍历数组并打印每个元素。
   • 每打印完一个数组后换行。

时间复杂度和空间复杂度

• 时间复杂度：冒泡排序的时间复杂度为 O(n²)，其中 n 是数组的长度。这是因为冒泡排序需要进行 n-1 次遍历，每次遍历最多需要进行 n-1 次比较和交换。
• 空间复杂度：冒泡排序的空间复杂度为 O(1)，因为它只需要常数级的额外空间。