考研数据结构——C语言实现冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较每对相邻元素，并在顺序错误的情况下交换它们。这个过程重复进行，直到没有需要交换的元素，这意味着列表已经排序完成。冒泡排序的名字来源于较小的元素会逐渐“冒泡”到列表的顶部（开始），而较大的元素沉到底部（末尾）。

下面是冒泡排序算法的详细步骤：

1. 开始排序：从数组的第一个元素开始，比较相邻的元素。
2. 比较和交换：如果当前元素大于下一个元素，就交换它们的位置。
3. 遍历数组：继续这个过程，直到到达数组的末尾。
4. 完成一轮遍历：在第一轮遍历结束后，最大的元素会被放置在数组的最后一个位置。
5. 重复过程：重复上述过程，但每次开始时都从数组的开始位置开始，直到数组完全排序。

在代码中，这个过程通过两层嵌套的for循环实现：

• 外层循环（for (i = 1; i < n; i++)）控制排序的轮数。每一轮都会将一个未排序的元素放到正确的位置。
• 内层循环（for (j = 0; j < n - i - 1; j++)）负责实际的比较和交换。i的值表示已经排序好的元素数量，因此在每一轮中，比较的次数会减少。

在内层循环中，如果a[j]大于a[j + 1]，就交换这两个元素的位置。这个过程会一直进行，直到内层循环完成，这意味着在当前轮次中，所有元素都已经被正确排序。

代码中的k变量用于临时存储一个元素的值，以便在交换时使用。

最后，使用另一个for循环遍历整个数组，并打印出排序后的元素。

需要注意的是，冒泡排序在最好的情况下（即数组已经是有序的）时间复杂度为O(n)，在最坏的情况下（即数组是逆序的）和平均情况下时间复杂度为O(n^2)，其中n是数组的长度。因此，对于大数据集，冒泡排序通常不是最有效的排序算法。

#include <stdio.h>
#include <stdlib.h>

int main() {
	int a[] = { 12,4,132,55,46,232,789,1,0,98,523,666 };
	int n = sizeof(a) / sizeof(a[0]);
	int i, j, k;
	for (i = 1; i < n; i++) {
		for (j = 0; j < n - 1; j++) {
			if (a[j] > a[j + 1]) {
				k = a[j];
				a[j] = a[j + 1];
				a[j + 1] = k;
			}
		}
	}
	for (i = 0; i < n; i++) {
		printf("%d", a[i]);
		printf(" ");
	}
	return 0;
}

结果如下：