C语言冒泡排序详解从原理到实战代码一步步教你实现高效排序算法

冒泡排序(Bubble Sort)是一种简单直观的排序算法,它通过重复遍历待排序的列表,比较相邻元素并交换它们的位置,使得较大的元素逐渐“冒泡”到列表的末尾。尽管冒泡排序在时间复杂度上不如快速排序或归并排序高效,但它对于初学者理解排序算法的基本原理非常有帮助。本文将从原理、实现、优化到实战代码,一步步教你如何用C语言实现冒泡排序,并探讨其高效性。
1. 冒泡排序的基本原理
冒泡排序的核心思想是通过相邻元素的比较和交换,将最大的元素逐步移动到数组的末尾。具体步骤如下:
遍历数组
:从数组的第一个元素开始,依次比较相邻的两个元素。
比较与交换
:如果前一个元素大于后一个元素,则交换它们的位置。
重复过程
:对每一对相邻元素重复上述操作,直到数组末尾。这样,最大的元素就会“冒泡”到数组的末尾。
缩小范围
:每完成一轮遍历,最大的元素已经就位,因此下一轮遍历的范围可以缩小一位。
终止条件
:当某一轮遍历中没有发生任何交换时,说明数组已经有序,可以提前终止排序。
1.1 示例说明
假设我们有一个数组
[5, 3, 8, 4, 2]
,我们希望通过冒泡排序将其升序排列。
第一轮遍历
:
比较 5 和 3:5 > 3,交换 →
[3, 5, 8, 4, 2]
比较 5 和 8:5 < 8,不交换 → [3, 5, 8, 4, 2] 比较 8 和 4:8 > 4,交换 →
[3, 5, 4, 8, 2]
比较 8 和 2:8 > 2,交换 →
[3, 5, 4, 2, 8]
第一轮结束,最大的元素 8 已经移动到末尾。
第二轮遍历
(范围缩小到前4个元素):
比较 3 和 5:3 < 5,不交换 → [3, 5, 4, 2, 8] 比较 5 和 4:5 > 4,交换 →
[3, 4, 5, 2, 8]
比较 5 和 2:5 > 2,交换 →
[3, 4, 2, 5, 8]
第二轮结束,次大的元素 5 移动到倒数第二位。
第三轮遍历
(范围缩小到前3个元素):
比较 3 和 4:3 < 4,不交换 → [3, 4, 2, 5, 8] 比较 4 和 2:4 > 2,交换 →
[3, 2, 4, 5, 8]
第三轮结束,第三大的元素 4 移动到倒数第三位。
第四轮遍历
(范围缩小到前2个元素):
比较 3 和 2:3 > 2,交换 →
[2, 3, 4, 5, 8]
第四轮结束,数组已经有序。
通过这个例子,我们可以看到冒泡排序是如何逐步将元素移动到正确位置的。
2. C语言实现冒泡排序
在C语言中,冒泡排序可以通过嵌套循环来实现。外层循环控制遍历的轮数,内层循环负责比较和交换相邻元素。
2.1 基础实现
以下是一个基础的冒泡排序函数,用于升序排列整数数组:
#include

void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; 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;
}
}
}
}

int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);

printf(“排序前的数组: “);
for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); bubbleSort(arr, n); printf("排序后的数组: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } 代码解释 : bubbleSort 函数接受一个整数数组 arr 和数组长度 n 作为参数。 外层循环 for (i = 0; i < n - 1; i++) 控制遍历的轮数,最多需要 n-1 轮。 内层循环 for (j = 0; j < n - i - 1; j++) 控制每轮遍历的范围,每轮遍历后,最大的元素已经就位,因此范围缩小一位。 如果 arr[j] > arr[j + 1]
,则交换两个元素。
main
函数中定义了一个示例数组,调用
bubbleSort
进行排序,并输出排序前后的结果。
运行结果
:
排序前的数组: 5 3 8 4 2
排序后的数组: 2 3 4 5 8
2.2 优化实现
基础冒泡排序有一个缺点:即使数组已经有序,它仍然会继续遍历和比较。我们可以通过引入一个标志位来优化,如果在某一轮遍历中没有发生任何交换,说明数组已经有序,可以提前终止排序。
#include

void bubbleSortOptimized(int arr[], int n) {
int i, j;
int swapped; // 标志位,记录是否发生交换
for (i = 0; i < n - 1; i++) { swapped = 0; // 每轮遍历前重置标志位 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;
swapped = 1; // 发生交换,设置标志位
}
}
// 如果没有发生交换,说明数组已经有序,提前退出
if (swapped == 0) {
break;
}
}
}

int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);

printf(“排序前的数组: “);
for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); bubbleSortOptimized(arr, n); printf("排序后的数组: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } 优化说明 : 引入 swapped 标志位,初始值为 0。 在每轮内层循环中,如果发生交换,则将 swapped 设置为 1。 在每轮外层循环结束后,检查 swapped 的值。如果为 0,说明没有发生交换,数组已经有序,使用 break 提前退出循环。 这种优化可以显著提高对部分有序数组的排序效率。 3. 冒泡排序的性能分析 3.1 时间复杂度 最好情况 :数组已经有序。在优化后的冒泡排序中,只需要进行一轮遍历(n-1 次比较),时间复杂度为 O(n)。 最坏情况 :数组完全逆序。需要进行 n-1 轮遍历,每轮比较次数递减,总比较次数为 (n-1) + (n-2) + … + 1 = n(n-1)/2,时间复杂度为 O(n²)。 平均情况 :随机数组,时间复杂度为 O(n²)。 3.2 空间复杂度 冒泡排序是原地排序算法,只需要常数级别的额外空间(用于交换元素的临时变量),因此空间复杂度为 O(1)。 3.3 稳定性 冒泡排序是稳定的排序算法,因为只有当相邻元素相等时才不会交换,相等元素的相对顺序不会改变。 4. 实战代码:冒泡排序的扩展应用 4.1 降序排序 只需修改比较条件即可实现降序排序: void bubbleSortDescending(int arr[], int n) { int i, j; int swapped; for (i = 0; i < n - 1; i++) { swapped = 0; 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; swapped = 1; } } if (swapped == 0) { break; } } } 4.2 对结构体数组排序 假设我们有一个学生结构体数组,需要根据成绩进行排序: #include
#include

typedef struct {
char name[50];
int score;
} Student;

void bubbleSortStudents(Student arr[], int n) {
int i, j;
int swapped;
for (i = 0; i < n - 1; i++) { swapped = 0; for (j = 0; j < n - i - 1; j++) { if (arr[j].score > arr[j + 1].score) { // 按成绩升序排序
// 交换整个结构体
Student temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0) {
break;
}
}
}

int main() {
Student students[] = {
{“Alice”, 85},
{“Bob”, 92},
{“Charlie”, 78},
{“David”, 95},
{“Eve”, 88}
};
int n = sizeof(students) / sizeof(students[0]);

printf(“排序前的学生列表:\n”);
for (int i = 0; i < n; i++) { printf("%s: %d\n", students[i].name, students[i].score); } printf("\n"); bubbleSortStudents(students, n); printf("排序后的学生列表:\n"); for (int i = 0; i < n; i++) { printf("%s: %d\n", students[i].name, students[i].score); } printf("\n"); return 0; } 运行结果 : 排序前的学生列表: Alice: 85 Bob: 92 Charlie: 78 David: 95 Eve: 88 排序后的学生列表: Charlie: 78 Alice: 85 Eve: 88 Bob: 92 David: 95 4.3 对字符串数组排序 冒泡排序也可以用于字符串数组的排序,使用 strcmp 函数进行比较: #include
#include

void bubbleSortStrings(char *arr[], int n) {
int i, j;
int swapped;
for (i = 0; i < n - 1; i++) { swapped = 0; for (j = 0; j < n - i - 1; j++) { if (strcmp(arr[j], arr[j + 1]) > 0) { // 按字典序升序排序
// 交换指针
char *temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0) {
break;
}
}
}

int main() {
char *words[] = {“banana”, “apple”, “cherry”, “date”, “elderberry”};
int n = sizeof(words) / sizeof(words[0]);

printf(“排序前的单词列表:\n”);
for (int i = 0; i < n; i++) { printf("%s\n", words[i]); } printf("\n"); bubbleSortStrings(words, n); printf("排序后的单词列表:\n"); for (int i = 0; i < n; i++) { printf("%s\n", words[i]); } printf("\n"); return 0; } 运行结果 : 排序前的单词列表: banana apple cherry date elderberry 排序后的单词列表: apple banana cherry date elderberry 5. 冒泡排序与其他排序算法的比较 5.1 与选择排序的比较 冒泡排序 :通过相邻元素的比较和交换,将最大元素逐步移动到末尾。 选择排序 :每次遍历找到最小元素,将其放到已排序序列的末尾。 性能 :两者的时间复杂度都是 O(n²),但选择排序的交换次数较少(最多 n-1 次),而冒泡排序在最坏情况下需要 O(n²) 次交换。 5.2 与插入排序的比较 插入排序 :将数组分为已排序和未排序两部分,每次将未排序部分的元素插入到已排序部分的正确位置。 性能 :插入排序在部分有序的数组上表现更好,时间复杂度可以达到 O(n),而冒泡排序在优化后也能达到 O(n)。 5.3 与快速排序的比较 快速排序 :基于分治思想,通过选择一个基准元素将数组分为两部分,递归排序。 性能 :快速排序的平均时间复杂度为 O(n log n),远优于冒泡排序的 O(n²),但冒泡排序更简单,适合小规模数据。 6. 总结 冒泡排序是一种简单易懂的排序算法,适合初学者学习排序算法的基本原理。通过本文的讲解,你应该已经掌握了冒泡排序的原理、C语言实现方法以及优化技巧。虽然冒泡排序在大规模数据上效率不高,但它在小规模数据或部分有序数据上仍然有其应用价值。 在实际编程中,可以根据数据规模和需求选择合适的排序算法。对于小规模数据,冒泡排序的简单性使其成为一个不错的选择;对于大规模数据,建议使用更高效的排序算法,如快速排序或归并排序。 希望本文能帮助你深入理解冒泡排序,并在实际编程中灵活运用。如果你有任何问题或需要进一步的解释,请随时提问!