泡泡排序是一种简单直观的排序算法。它重复地遍历待排序的列表,比较每对相邻元素,如果它们的顺序错误就把它们交换过来。遍历列表的工作重复地进行,直到没有再需要交换的元素,也就是说该列表已经排序完成。
以下是使用C语言实现泡泡排序的一个基本示例:
基本原理
在每一次遍历中,相邻元素被进行比较,如果左边的元素比右边的元素大(或小,取决于是升序还是降序排序),则交换它们的位置。这个过程会一直持续,直到整个列表都被“气泡”到正确的顺序。
代码实现
首先,我们需要定义一个交换函数,因为我们会经常交换元素:
#include <stdio.h>
// 函数用于交换两个整数的值
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
然后,我们编写泡泡排序的主函数:
void bubbleSort(int arr[], int n) {
int i, j;
bool swapped;
for (i = 0; i < n-1; i++) {
swapped = false;
// 遍历数组从第一个元素到第 n-i-1 个元素
for (j = 0; j < n-i-1; j++) {
// 如果当前元素比下一个元素大,交换它们
if (arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
// 如果这一轮没有发生任何交换,那么列表已经排序完成
if (swapped == false)
break;
}
}
主函数
现在我们创建一个主函数,用于测试我们的泡泡排序:
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
for (int i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
运行和测试
当你将上面的代码保存为一个 .c 文件并编译运行时,你应该能看到如下输出:
Sorted array:
11 12 22 25 34 64 90
总结
通过上面的例子,我们了解了泡泡排序的基本原理,并学会了如何用C语言编写一个简单的泡泡排序程序。泡泡排序虽然简单,但是它的效率并不是特别高,对于大数据量的排序来说可能并不是最佳选择。尽管如此,它对于教学排序算法的基础概念是非常有用的。
