排序算法是计算机科学中最基础也是最重要的算法之一。在众多排序算法中，冒泡排序（Bubble Sort）以其简单直观的特点，成为许多编程初学者的入门首选。本文将详细介绍C语言中冒泡排序的实现原理、代码实现以及相关的优化技巧。
冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行，直到没有再需要交换的元素为止。
冒泡排序的工作原理可以通过以下步骤理解：
让我们通过一个具体的例子来理解冒泡排序的过程：
原始数组: [5, 2, 8, 1, 9]
第一轮:
- 比较 5 和 2: [2, 5, 8, 1, 9]
- 比较 5 和 8: [2, 5, 8, 1, 9] (不交换)
- 比较 8 和 1: [2, 5, 1, 8, 9]
- 比较 8 和 9: [2, 5, 1, 8, 9] (不交换)
第二轮:
- 比较 2 和 5: [2, 5, 1, 8, 9] (不交换)
- 比较 5 和 1: [2, 1, 5, 8, 9]
- 比较 5 和 8: [2, 1, 5, 8, 9] (不交换)
第三轮:
- 比较 2 和 1: [1, 2, 5, 8, 9]
结果: [1, 2, 5, 8, 9]#include <stdio.h>
// 冒泡排序基础版本
void bubbleSort(int arr[], int n) {
int i, j, temp;
// 外层循环控制排序轮数
for (i = 0; i < n - 1; i++) {
// 内层循环控制每轮比较次数
for (j = 0; j < n - i - 1; j++) {
// 如果前一个元素大于后一个元素，则交换
if (arr[j] > arr[j + 1]) {
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("原始数组: ");
printArray(arr, n);
bubbleSort(arr, n);
printf("排序后数组: ");
printArray(arr, n);
return 0;
}输出结果:
原始数组: 64 34 25 12 22 11 90
排序后数组: 11 12 22 25 34 64 90#include <stdbool.h> // 需要引入stdbool.h
// 优化版本：如果某轮没有发生交换，说明已经有序
void bubbleSortOptimized(int arr[], int n) {
int i, j, temp;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明数组已经有序
if (!swapped) {
break;
}
}
}// 优化版本：记录最后交换的位置，减少比较次数
void bubbleSortAdvanced(int arr[], int n) {
int i, j, temp;
int lastSwapPos = 0;
int sortBorder = n - 1;
for (i = 0; i < n - 1; i++) {
bool isSorted = true;
for (j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false;
lastSwapPos = j;
}
}
sortBorder = lastSwapPos;
if (isSorted) {
break;
}
}
}| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n) | 数组已经有序，只需一轮遍历 |
| 平均情况 | O(n²) | 随机顺序的数组 |
| 最坏情况 | O(n²) | 数组完全逆序 |
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <stdlib.h>
// 函数声明
void bubbleSort(int arr[], int n);
void bubbleSortOptimized(int arr[], int n);
void bubbleSortAdvanced(int arr[], int n);
void printArray(int arr[], int size);
void generateRandomArray(int arr[], int n);
void copyArray(int source[], int dest[], int n);
void comparePerformance(int arr[], int n);
// 基础冒泡排序
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 优化版冒泡排序
void bubbleSortOptimized(int arr[], int n) {
int i, j, temp;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
// 高级优化版冒泡排序
void bubbleSortAdvanced(int arr[], int n) {
int i, j, temp;
int lastSwapPos = 0;
int sortBorder = n - 1;
for (i = 0; i < n - 1; i++) {
bool isSorted = true;
for (j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false;
lastSwapPos = j;
}
}
sortBorder = lastSwapPos;
if (isSorted) break;
}
}
// 打印数组
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 生成随机数组
void generateRandomArray(int arr[], int n) {
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
}
// 复制数组
void copyArray(int source[], int dest[], int n) {
for (int i = 0; i < n; i++) {
dest[i] = source[i];
}
}
// 性能比较
void comparePerformance(int arr[], int n) {
int arr1[n], arr2[n], arr3[n];
clock_t start, end;
double cpu_time_used;
// 复制数组用于不同版本的测试
copyArray(arr, arr1, n);
copyArray(arr, arr2, n);
copyArray(arr, arr3, n);
printf("性能比较 (数组大小: %d):\n", n);
printf("----------------------------------------\n");
// 基础版本
start = clock();
bubbleSort(arr1, n);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("基础版本耗时: %.6f 秒\n", cpu_time_used);
// 优化版本
start = clock();
bubbleSortOptimized(arr2, n);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("优化版本耗时: %.6f 秒\n", cpu_time_used);
// 高级优化版本
start = clock();
bubbleSortAdvanced(arr3, n);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("高级优化版本耗时: %.6f 秒\n", cpu_time_used);
printf("----------------------------------------\n");
}
// 主函数
int main() {
int choice, n;
printf("C语言冒泡排序算法演示程序\n");
printf("=====================================\n");
while (1) {
printf("\n请选择操作:\n");
printf("1. 手动输入数组并排序\n");
printf("2. 随机生成数组并排序\n");
printf("3. 性能测试\n");
printf("4. 退出程序\n");
printf("请输入选择 (1-4): ");
scanf("%d", &choice);
switch (choice) {
case 1: {
printf("请输入数组大小: ");
scanf("%d", &n);
int arr[n];
printf("请输入 %d 个整数:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\n原始数组: ");
printArray(arr, n);
bubbleSortOptimized(arr, n);
printf("排序后数组: ");
printArray(arr, n);
break;
}
case 2: {
printf("请输入数组大小: ");
scanf("%d", &n);
int arr[n];
generateRandomArray(arr, n);
printf("\n原始数组: ");
printArray(arr, n);
bubbleSortOptimized(arr, n);
printf("排序后数组: ");
printArray(arr, n);
break;
}
case 3: {
printf("请输入测试数组大小: ");
scanf("%d", &n);
int arr[n];
generateRandomArray(arr, n);
comparePerformance(arr, n);
break;
}
case 4:
printf("感谢使用，再见！\n");
return 0;
default:
printf("无效选择，请重新输入！\n");
}
}
return 0;
}// 带调试信息的冒泡排序
void bubbleSortWithDebug(int arr[], int n) {
int i, j, temp;
int pass = 1;
printf("开始排序过程:\n");
for (i = 0; i < n - 1; i++) {
printf("\n第 %d 轮排序:\n", pass++);
printf("排序前: ");
printArray(arr, n);
for (j = 0; j < n - i - 1; j++) {
printf("比较 %d 和 %d", arr[j], arr[j+1]);
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
printf(" -> 交换");
} else {
printf(" -> 不交换");
}
printf("\n");
}
printf("排序后: ");
printArray(arr, n);
}
}冒泡排序虽然简单，但理解它对学习更复杂的排序算法很有帮助。通过本文的学习，你应该掌握了：
希望这篇教程对你学习C语言和排序算法有所帮助！如果你有任何问题或建议，欢迎在评论区留言讨论。
参考资源: