044 冒泡排序 C语言 冒泡排序 C语言

冒泡排序是一种基础且经典的排序算法，主要应用于计算机科学领域，特别是在编程语言如C语言中。这个算法通过不断地比较相邻元素并交换位置，使得每一轮排序后最大（或最小）的元素“浮”到数组的一端，从而实现整体的排序。在C语言中，我们通常会用到指针和循环来实现冒泡排序。 冒泡排序的基本思想是重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经过交换慢慢“浮”到数列的顶端，就像水中的气泡最终会上浮到水面一样。 在C语言中，实现冒泡排序的步骤如下： 1. 定义一个数组，存储待排序的数据。 2. 获取数组长度，通常用`sizeof`运算符结合数组类型和数组名来计算。 3. 使用一个外层循环控制排序的轮数，从第一轮到倒数第二轮。 4. 在每一轮中，使用一个内层循环进行相邻元素的比较和交换。从数组的第一个元素开始，一直比较到最后两个元素。 5. 在内层循环中，每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。 6. 经过一轮排序，最大的元素会被移动到数组的最后。所以，下一轮比较可以忽略掉最后一个元素，减少比较的次数。 7. 这个过程不断重复，直到所有元素都有序。 C语言实现冒泡排序的代码示例如下： ```c #include <stdio.h> void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n - 1; i++) { // 外层循环控制轮数 for (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; // 交换元素 } } } } void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组：\n"); printArray(arr, n); bubbleSort(arr, n); printf("排序后的数组：\n"); printArray(arr, n); return 0; } ``` 在上述代码中，`bubbleSort`函数实现了冒泡排序，`printArray`函数用于打印数组。`main`函数中定义了一个待排序的数组，调用`bubbleSort`进行排序，然后打印排序结果。 需要注意的是，冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)，在处理大量数据时效率较低。但在某些特定情况下，例如部分有序的数组，冒泡排序可能会有较好的表现。此外，通过对算法进行优化，如设置标志位来判断是否进行了交换，可以在已排序的情况下提前结束排序，提高效率。