排序算法‌ 之‌ ‌‌‌冒泡排序（Bubble Sort）

排序算法‌ 之‌ ‌‌‌冒泡排序（Bubble Sort）

1. 基础概念

1.1 冒泡排序的定义

冒泡排序是一种通过重复比较相邻元素并交换它们的位置，逐步将未排序的部分中最大（或最小）的元素“冒泡”到数组末尾的排序算法。它属于比较排序，典型为稳定排序。

1.2 冒泡排序的特点

• 算法分类：内部排序，基于交换的比较排序。
• 稳定性：稳定排序（相同的元素排序后相对位置不变）。
• 时间复杂度：最坏和平均情况为 O(n²)，最好情况为 O(n)。
• 空间复杂度：O(1)（原地排序）。
• 实现简单，但性能较低，适用于数据规模较小的场景。

1.3 使用场景

冒泡排序适用于以下场景：

• 需要实现简单且容易理解的排序功能时。
• 数据量较小且几乎有序时。
• 作为排序算法学习的入门算法。

2. 实现与操作

2.1 核心操作实现

以下代码展示了冒泡排序的核心操作实现：

#include <stdio.h> // 冒泡排序函数 void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // 提前退出标志 int swapped = 0; 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; swapped = 1; // 发生交换 } } // 如果没有发生交换，说明已排序好 if (!swapped) { break; } } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; 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("排序前的数组: "); printArray(arr, n); bubbleSort(arr, n); printf("排序后的数组: "); printArray(arr, n); return 0; } </stdio.h>

2.2 代码详解

• bubbleSort 函数实现了冒泡排序，通过两层循环遍历数组。
• 在每次内层循环中，比较相邻元素并交换位置，较大的元素逐步向右“冒泡”。
• 设置 swapped 标志，若一次完整遍历未发生交换，直接退出循环，优化性能。
• 通过 printArray 函数打印数组，用于显示排序前后的结果。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 最坏情况：O(n²)，适用于完全逆序的数组。
• 平均情况：O(n²)，适用于随机排列的数组。
• 最好情况：O(n)，适用于已排序的数组（优化后检测交换标志）。

3.2 空间复杂度

冒泡排序使用原地排序算法，不需要额外的存储空间，空间复杂度为 O(1)。

4. 优缺点与局限性

4.1 优点

• 实现简单，易于理解和编码。
• 对小型数组性能尚可。
• 可通过标志位优化检测提前结束。

4.2 缺点与局限性

• 时间复杂度较高，效率低，适用于小规模数据。
• 对于大规模数据，性能远不如快速排序、归并排序等高效算法。

5. 常见应用场景

5.1 实际应用

以下代码展示了对小型数组排序的应用：

#include <stdio.h> // 冒泡排序函数（求Top-K最小元素） void bubbleSortTopK(int arr[], int n, int k) { for (int i = 0; i < k; 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; } } } } // 打印Top-K元素 void printTopK(int arr[], int k) { for (int i = 0; i < k; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {10, 5, 8, 3, 1, 7}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; bubbleSortTopK(arr, n, k); printf("Top-%d 最小元素: ", k); printTopK(arr, k); return 0; } </stdio.h>

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc -o bubble_sort bubble_sort.c

6.2 测试用例

输入数组为 {64, 34, 25, 12, 22, 11, 90}，输出结果为：

排序前的数组: 64 34 25 12 22 11 90
排序后的数组: 11 12 22 25 34 64 90