C语言冒泡排序函数详解：从基础到优化78

冒泡排序 (Bubble Sort) 是一种简单直观的排序算法，其核心思想是反复遍历待排序的数组，比较相邻元素的大小，并将较大的元素交换到数组的末尾。尽管其时间复杂度较高，并不适用于大型数据集，但由于其代码简洁易懂，在学习算法的过程中经常被用作入门算法。本文将详细介绍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次，内层循环比较相邻元素并交换。如果arr[j]大于arr[j+1]，则交换这两个元素。每次外层循环结束后，数组的最大元素都会被移动到其最终位置。 main函数演示了如何使用该函数。

二、算法分析

冒泡排序的时间复杂度在最坏和平均情况下都是O(n²)，最佳情况下为O(n)（当数组已排序时）。空间复杂度为O(1)，因为它只使用常数个额外空间。由于其二次时间复杂度，冒泡排序不适合处理大量数据。但是，它易于理解和实现，适合作为学习算法的基础。

三、优化策略

虽然冒泡排序本身效率不高，但我们可以通过一些优化策略来提高其性能：

1. 添加标志位：

在每一轮遍历中，如果没有任何交换发生，则说明数组已排序，可以提前结束排序过程。这可以显著减少不必要的比较次数。```c
void bubbleSortOptimized(int arr[], int n) {
int i, j, temp, swapped;
for (i = 0; i < n - 1; i++) {
swapped = 0;
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 = 1;
}
}
if (swapped == 0)
break;
}
}
```