大家好！我们又见面了！计算机代码的实现都是靠一个一个算法实现的，今天就给小伙伴们介绍一种非常简单的算法---冒泡排序，冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它反复的将需要排序的数列一直两两进行排序，每次只比较两个元素，如果顺序不对就将他们交换，重复进行直到没有元素还需要交换，此时，也就表示数列的排序已经完成。这个算法名字的由来是因为小的元素会像“泡泡”一样通过一次次交换慢慢的“浮”到数列的最顶端位置。作为最简单的算法之一，与我们而言就好像在四级词汇中看到“abandon”一样，非常简单但是常见，因此最为我们熟悉。
可能文字对于这种算法描述还是太过生涩难懂，那么我将具一个通俗易懂的例子：
有数组arr[10]={10,9,8,7,6,5,4,3,2,1}这样十个整形的数字，此时我们需要从小到大进行排序，我们选择采取冒泡排序。
10 9 8 7 6 5 4 3 2 1 10与9进行比较，发现10>9，则改变数组为9 10 8 7 6 5 4 3 2 1；
9 10 8 7 6 5 4 3 2 1 再10与8进行比较，发现10>8，则改变数组为9 8 10 7 6 5 4 3 2 1；
9 8 10 7 6 5 4 3 2 1 再10与7进行比较，发现10>7，则改变数组为9 8 7 10 6 5 4 3 2 1；
9 8 7 10 6 5 4 3 2 1 再10与6进行比较，发现10>6，则改变数组为9 8 7 6 10 5 4 3 2 1；
9 8 7 6 10 5 4 3 2 1 再10与5进行比较，发现10>5，则改变数组为9 8 7 6 5 10 4 3 2 1；
......
最终结果变成9 8 7 6 5 4 3 2 1 10，这时仅仅只是完成了第一轮冒泡排序。
当数组arr变成9 8 7 6 5 4 3 2 1 10时，开始第二轮冒泡排序。
9 8 7 6 5 4 3 2 1 10 9与8进行比较，发现9>8，则改变数组为8 9 7 6 5 4 3 2 1 10；
8 9 7 6 5 4 3 2 1 10 再9与7进行比较，发现9>7，则改变数组为8 7 9 6 5 4 3 2 1 10；
8 7 9 6 5 4 3 2 1 10 再9与6进行比较，发现9>6，则改变数组为8 7 6 9 5 4 3 2 1 10；
8 7 6 9 5 4 3 2 1 10 再9与5进行比较，发现9>5，则改变数组为8 7 6 5 9 4 3 2 1 10；
8 7 6 5 9 4 3 2 1 10 再9与4进行比较，发现9>4，则改变数组为8 7 6 5 4 9 3 2 1 10；
......
最终结果变成8 7 6 5 4 3 2 1 9 10，这时完成了第二轮冒泡排序。
当数组arr变成8 7 6 5 4 3 2 1 9 10时，开始第三轮冒泡排序。
我们不难发现结果最终成为了7 6 5 4 3 2 1 8 9 10。
......
最终经过9轮排序最终成功得到1 2 3 4 5 6 7 8 9 10。
通过这个例子大家肯定明白冒泡排序到底是怎么一回事，大家想想看这个排序方法什么时候最快？什么时候最慢？当它正序排序的时候最快，因为根本不需要，冒泡排序，而上面的例子（反序）这个时候就是最慢，此时我们写个for循环不应该更快吗？其实并不是没有道理，所以冒泡排序其实很简单也很“笨”。不过这样“笨笨的”冒泡排序也并不是毫无优点可言，不然它就没有存在的必要。
时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin=n-1,Mmin=0。所以，冒泡排序最好的时间复杂度为O(n)。若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值:
Cmax=n(n-1)/2=O(n^2)
Mmax=3n(n-1)/2=O(n^2)
冒泡排序的最坏时间复杂度为O(n^2) 。综上，因此冒泡排序总的平均时间复杂度为O(n^2)。
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
下面给大家带来代码展示：
#include <stdio.h>
#include <string.h>
void Sort(int *arr, int sz)
{
int i = 0;
//趟数
for (i = 0; i < sz-1; i++)
{
int j = 0;
//每次冒泡排序都会使得最后一个数正确，每趟需要两两比较的次数都会减1
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main()
{
int arr[] = { 8,5,1,7,9,4,0,3,2,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
Sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}运行结果正是我们想要的结果：
那么到这里给大家分享的第一种算法到这里也就结束了，欢迎大家点赞收藏！
