从零开始完成冒泡排序（0基础）——C语言版

前言

在学习编程的过程中，排序算法是必须要掌握的知识之一。冒泡排序作为一种简单易懂的排序算法，非常适合初学者入门。今天，我们就从零开始，一起学习如何用C语言完成冒泡排序。

一、冒泡排序的基本思想

冒泡排序的基本思想是通过相邻元素之间的比较和交换，将最大的元素逐步移动到序列的末尾。就像水中的气泡一样，较小的元素会逐渐“浮”到序列的前面，而较大的元素会“沉”到序列的后面，因此得名冒泡排序。

举个生活中的例子，假设有5个人排成一列，他们想按照身高从矮到高排队。于是，第一个人和第二个人比较身高，如果第一个人比第二个人高，他们就交换位置；否则保持原位。接着，第二个人和第三个人进行比较和交换，依此类推，直到倒数第二个人和最后一个人比较。这样一轮下来，最高的人就会被“冒泡”到队伍的最后面。接下来，再对前面的4个人重复这个过程，直到所有人都排好序。

二、冒泡排序的执行过程

为了更好地理解冒泡排序，我们以一个具体的例子来说明。假设我们有这样一个数组：[5, 3, 8, 1, 2]，我们要对其进行升序排序。

（一）第一轮排序

1. 比较5和3，因为5>3，所以交换位置，数组变为[3,5,8,1,2]。
2. 比较5和8，因为5<8，所以不交换位置，数组仍为[3,5,8,1,2]。
3. 比较8和1，因为8>1，所以交换位置，数组变为[3,5,1,8,2]。
4. 比较8和2，因为8>2，所以交换位置，数组变为[3,5,1,2,8]。

经过第一轮排序后，最大的元素8被移动到了数组的最后面。

（二）第二轮排序

1. 比较3和5，因为3<5，所以不交换位置，数组仍为[3,5,1,2,8]。
2. 比较5和1，因为5>1，所以交换位置，数组变为[3,1,5,2,8]。
3. 比较5和2，因为5>2，所以交换位置，数组变为[3,1,2,5,8]。

经过第二轮排序后，第二大的元素5被移动到了数组的倒数第二位。

（三）第三轮排序

1. 比较3和1，因为3>1，所以交换位置，数组变为[1,3,2,5,8]。
2. 比较3和2，因为3>2，所以交换位置，数组变为[1,2,3,5,8]。

经过第三轮排序后，第三大的元素3被移动到了数组的倒数第三位。

（四）第四轮排序

比较1和2，因为1<2，所以不交换位置，数组仍为[1,2,3,5,8]。

经过四轮排序后，整个数组已经有序，排序完成。

三、冒泡排序的代码实现（C语言）

（一）代码实现

以下是用C语言实现的冒泡排序代码：

#include <stdio.h>void bubble_sort(int arr[], int n) {// 外层循环控制排序的轮数for(int i = 0; i < n-1; i++) {// 内层循环控制每轮中相邻元素的比较和交换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;}}}
}int main() {int arr[] = {5, 3, 8, 1, 2};int n = sizeof(arr)/sizeof(arr[0]);printf("排序前的数组：");for(int i = 0; i < n; i++) {printf("%d ", arr[i]);}bubble_sort(arr, n);printf("\n排序后的数组：");for(int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

（二）代码解析

1. #include <stdio.h>：引入标准输入输出库，用于使用printf等函数。
2. void bubble_sort(int arr[], int n)：定义了一个名为bubble_sort的函数，用于对数组进行冒泡排序。其中，arr是要排序的数组，n是数组的长度。
3. 外层循环for(int i = 0; i < n-1; i++)：控制排序的轮数。因为每一轮都会将最大的元素移到数组末尾，所以需要进行n-1轮排序。
4. 内层循环for(int j = 0; j < n-i-1; j++)：控制每轮中相邻元素的比较和交换。因为每一轮结束后，最后i个元素已经是有序的，所以内层循环的范围逐渐缩小。
5. if(arr[j] > arr[j+1])：比较相邻的两个元素，如果前者大于后者，则需要交换位置。
6. 交换元素的位置：通过临时变量temp来交换arr[j]和arr[j+1]的值。
7. int main()：主函数，程序的入口。
8. int arr[] = {5, 3, 8, 1, 2};：定义了一个要排序的数组。
9. int n = sizeof(arr)/sizeof(arr[0]);：计算数组的长度。
10. printf：用于输出数组的值，方便我们查看排序前后的结果。
11. bubble_sort(arr, n);：调用冒泡排序函数，对数组进行排序。

四、冒泡排序的时间复杂度和空间复杂度

（一）时间复杂度

冒泡排序的时间复杂度取决于数组的初始状态。在最坏情况下，即数组完全逆序时，需要进行n-1轮比较，每轮比较的次数分别为n-1、n-2、…、1次，总比较次数为(n-1)+(n-2)+…+1 = n(n-1)/2，因此最坏时间复杂度为O(n²)。在最好情况下，即数组已经有序时，只需要进行一轮比较，比较次数为n-1次，因此最好时间复杂度为O(n)。平均时间复杂度也为O(n²)。

（二）空间复杂度

冒泡排序是一种原地排序算法，只需要一个临时变量来交换元素的位置，因此空间复杂度为O(1)。

五、冒泡排序的优化

（一）设置标志位

在冒泡排序的过程中，如果某一轮没有发生任何交换操作，说明数组已经有序，可以提前结束排序。为此，我们可以设置一个标志位flag，在内层循环开始前将其置为0，如果发生了交换操作则将其置为1。每一轮结束后，如果flag仍为0，就直接跳出外层循环。

优化后的C代码如下：

#include <stdio.h>void bubble_sort_optimized(int arr[], int n) {// 外层循环控制排序的轮数for(int i = 0; i < n-1; i++) {int flag = 0;  // 设置标志位// 内层循环控制每轮中相邻元素的比较和交换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;flag = 1;  // 发生交换，置为1}}if(flag == 0) {  // 如果没有发生交换，提前结束break;}}
}int main() {int arr[] = {5, 3, 8, 1, 2};int n = sizeof(arr)/sizeof(arr[0]);printf("排序前的数组：");for(int i = 0; i < n; i++) {printf("%d ", arr[i]);}bubble_sort_optimized(arr, n);printf("\n排序后的数组：");for(int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

（二）减少内层循环的范围

在每一轮排序中，最后i个元素已经是有序的，因此内层循环的范围可以进一步缩小，即从0到n-i-1。这样可以减少不必要的比较操作，提高算法的效率。

六、总结

通过本文的学习，我们从零开始，详细介绍了冒泡排序的基本思想、执行过程、C语言代码实现以及优化方法。冒泡排序作为一种简单的排序算法，虽然在实际应用中可能不如快速排序、归并排序等高效，但对于初学者来说，它是一个很好的入门算法，帮助我们理解排序算法的基本原理和实现方法。希望读者能够通过本文的学习，掌握冒泡排序的精髓，并在今后的学习中逐步深入，探索更多高效的排序算法。