冒泡排序(Bubble Sort)是一种基础的比较排序算法,它主要通过不断比较并交换相邻元素来实现对数组或列表的排序。在C语言中,我们可以用以下方式实现冒泡排序:
首先,定义一个名为`bubbleSort`的函数,接受一个整型数组`arr`和它的长度`n`作为参数。在函数内部,我们使用两个嵌套的`for`循环来遍历数组。外层循环控制遍历的轮数,内层循环则是进行相邻元素的比较和交换。这里引入了一个`swapped`标志变量,用来检测在一轮遍历中是否发生了元素交换。如果一轮遍历下来没有元素交换,说明数组已经有序,可以提前结束排序。
```c
void bubbleSort(int arr[], int n) {
int temp;
int swapped;
for (int i = 0; i < n - 1; i++) {
swapped = 0; // 标志变量,用于检测是否发生了交换
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换arr[j]和arr[j+1]的位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1; // 表示发生了交换
}
}
// 如果一轮遍历没有发生交换,说明数组已经有序,可以提前退出
if (swapped == 0) {
break;
}
}
}
```
在主函数`main`中,我们创建了一个整型数组`arr`,并初始化了一些随机值。接着,计算数组的长度`n`,并打印出未排序的数组。调用`bubbleSort`函数对数组进行排序,然后再次打印排序后的数组。
```c
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("未排序数组:\n");
for (int i = 0; i < n; i++) {
printf("%d", arr[i]);
}
bubbleSort(arr, n);
printf("\n排序后的数组:\n");
for (int i = 0; i < n; i++) {
printf("%d", arr[i]);
}
return 0;
}
```
冒泡排序的时间复杂度是O(n^2),这意味着它在处理大型数据集时效率较低。然而,由于其简单易懂的实现,冒泡排序常被用作教学示例。此外,冒泡排序是稳定的排序算法,即相等的元素在排序后保持原有的相对顺序。在实际应用中,对于小规模或者部分有序的数据,冒泡排序可能仍有其适用性。