当前位置：首页 > article >正文

C 语言冒泡排序算法详解

article 2024/11/13 18:27:24

C 语言冒泡排序算法详解

引言

工作原理

示例代码

代码解释

时间复杂度和空间复杂度

C 语言冒泡排序算法详解

引言

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

工作原理

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

具体步骤如下：

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

示例代码

下面是一个用 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;
}

代码解释

主函数 main：
- 定义一个整数数组 arr 并初始化。
- 计算数组的长度 n。
- 打印原始数组。
- 调用 bubbleSort 函数对数组进行排序。
- 打印排序后的数组。
冒泡排序函数 bubbleSort：
- 使用两个嵌套的 for 循环来遍历数组。
- 外部循环控制遍历次数。
- 内部循环用于比较和交换相邻的元素。
- 如果前一个元素大于后一个元素，则交换它们的位置。
打印数组函数 printArray：
- 遍历数组并打印每个元素。
- 每打印完一个数组后换行。