1.冒泡排序的定义
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端，但是在广泛适用后，冒泡排序可以用来排任意顺序。
2.冒泡排序的原理
假设要将已知无需数列按从小到大排列，将第一个元素与后面的元素依次比较，如果必后面的元素小，就与后面某个元素交换位置，然后用这个元素再依次往后比较，遇到比这个元素小的就与这个元素交换，直到最后一个元素，就完成了一趟冒泡排序，则最后一个元素一定是这个序列里最大的一个元素；然后开始第二趟冒泡排序，继续从第一个元素开始往后一次比较，遇到较小的就交换位置，直到倒数第二个数，那么最后倒数第二个数就变成了第二大的数.......依次排完序列中所有的数，那么这个数的顺序就会变成从小到大，下面我用图来演示
第一趟冒泡排序，是对序列中所有数进行操作
第 i 趟冒泡排序，是对序列中除最后一个数外（10-i）个数进行操作
3.代码及其解析
#include<stdio.h> int main() { int arr[10] = { 10,9,8,7,6,11,4,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数 int i = 0; printf("排序前的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); for (i = 0; i < sz - 1; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } printf("排序后的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
运行结果：
代码解析：外部循环控制冒泡排序的趟数，for循环从0开始，循环sz-1（数组元素-1）次，内部循环控制每次具体的冒泡排序过程，因为每趟冒泡排序需要进行比较的次数递减，所以在循环的控制条件那再减去i来控制每趟冒泡排序进行的比较次数。在内部循环的循环体内，对这趟冒泡排序需要排序的元素进行遍历，小的元素放前面，大的逐次往后走，没趟冒泡结束后都能确定一个元素的位置。（sz-1）趟冒泡排序结束后，冒泡排序及就结束了。当然，如果想进行从大到小排序，只需要改变冒泡排序的判断部分，将大的元素放前面，小的元素往后走即可，代码如下：
#include<stdio.h> int main() { int arr[10] = { 10,9,8,7,6,11,4,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数 int i = 0; printf("排序前的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); for (i = 0; i < sz - 1; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { if (arr[j] < arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } printf("排序后的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
运行结果：
4.冒泡排序的改进
由于冒泡排序的时间复杂度实在太高，所以冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。
#include<stdio.h> int main() { int arr[10] = { 10,9,8,7,6,11,4,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数 int i = 0; printf("排序前的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); int flag = 0; for (i = 0; i < sz - 1; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { if (arr[j] >arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag++; } } if(flag==0) break; } printf("排序后的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
方法就是在每次冒泡后，检验一下到底这趟冒泡排序有没有交换顺序，如果没有的话，那么flag的值没有发生变化，就可以直接退出循环，这种方法可以略微提升一下效率。
5.实现冒泡排序函数
用函数实现冒泡排序，传参方法跟数组传参相同，具体可参考C语言函数详解
里面有具体介绍数组传参的方法，这里就直接上代码
#include<stdio.h> void Bubble_Sort(int arr[], int sz) { int flag = 0; int i = 0; for (i = 0; i < sz - 1; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag++; } } if (flag == 0) break; } } int main() { int arr[10] = { 10,9,8,7,6,11,4,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数 int i = 0; printf("排序前的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); Bubble_Sort(arr, sz); printf("排序后的数组:"); for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
本文收录于基础算法 、C语言学习专题 、水火莲花-C疑难专题
文章知识点与官方知识档案匹配，可进一步学习相关知识
