C语言冒泡排序详解：从入门到进阶368

冒泡排序 (Bubble Sort) 是一种简单的排序算法，它重复地走访要排序的列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访列表的工作是重复进行直到没有再需要交换，也就是说列表已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到顶端。

虽然冒泡排序的效率不高，时间复杂度在最坏和平均情况下都是 O(n²)，但在理解排序算法的基本原理以及教学方面，它仍然是一个非常好的例子。它易于理解和实现，非常适合初学者学习。本文将详细讲解C语言中冒泡排序的实现，并讨论其优缺点以及一些改进方法。

基本实现

下面是一个简单的C语言函数，实现了冒泡排序： ```c
#include
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;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}
```

这段代码首先定义了一个bubbleSort函数，它接收一个整数数组arr和数组大小n作为输入。外循环迭代n-1次，内循环迭代n-i-1次。在内循环中，它比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们。每一次外循环迭代，都会将最大的未排序元素移动到其正确的位置。

算法优化

上述基本实现可以进行一些优化，以提高效率。一个常见的优化是增加一个标志位，用于指示在某一轮迭代中是否进行了交换。如果在某一轮迭代中没有进行任何交换，则说明数组已经排序完成，可以提前结束排序过程。```c
#include
#include
void bubbleSortOptimized(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
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 = true;
}
}
if (!swapped)
break;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSortOptimized(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}
```