冒泡排序
文章目录
- [1. 前言](https://cloud.tencent.com/developer)
- [2. 冒泡算法](https://cloud.tencent.com/developer)
- [3. 冒泡排序算法的原理总结](https://cloud.tencent.com/developer)
- [4. 代码](https://cloud.tencent.com/developer)
1. 前言
轮子哥曾经在知乎里讲过这么一个事，当年他毕业的时候，有一个公司（微软）来上海招聘。第一轮笔试出的算法题是冒泡排序，全场只有一半的学生写了出来。
你可能会疑问冒泡怎么简单，怎么可能，哈哈，别急，冒泡排序虽然是最简单的算法，但是如果现在让屏幕前的你写，能立马写出来的在下面评论！所以往往看似越简单的东西，越是能考查我们的基本功。这篇文章，就让小编带你学习一下冒泡排序吧。
2. 冒泡算法
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序的算法复杂度为n^2，如果不了解什么是算法复杂度，可以先看一下这篇：算法复杂度
现在通过一个动态图，让我们看一下冒泡排序的工作过程：
这个动态图演示了一个无序数组使用冒泡排序转变为一个从大到小的有序数组，让我们来观察一下，到第一个变黄的元素3，这期间经历了什么，我们暂且把这个数组称为A，A0和A1比较，A0里面的元素（值）小于A1，交换元素，交换完之后，A1与A2两个相邻的两个元素比较，左边又小于右边，交换元素，交换完之后，A2与A3两个相邻的两个元素比较，左边是12，右边是3，左边比右边大，不交换元素，之后接着进行A3和A4的对比等等。。。
好了，那现在我问你，到第一个变黄的元素3，这期间经历了几次比较？千万不要告诉我是6次，是5次，记住了！隔壁老王家8岁的孩子都知道5个手指之间有四个空隙，是两两比较，不要搞错喽，小编怕你被文字搞糊涂了，熬夜给你做了图，这下图文应该明白吧。
所以第一次循环应该是5次，并且最后的元素应该会是最小的元素，要记住哦。之后就是重复上述的步骤，只不过把最后一个排除，因为上文提到过，最后一个元素应该会是最小的数，所以之后的循环次数依次为:4次，3次，2次。到这里，我们的无序数组就会经过冒泡排序变成了有序数组。
3. 冒泡排序算法的原理总结
1 比较相邻的元素。如果第一个比第二个小，就交换他们两个。 2 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3 针对所有的元素重复以上的步骤，除了最后一个。 4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
4. 代码
int array[] = {7,10,12,3,9,5};
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6 - i - 1; j++)
{
if (array[j] < array[j + 1])
{
int tamp = array[j];
array[j] = array[j + 1];
array[j + 1] = tamp;
}
}
} 要说的就是注意第二层循环的条件，千万不要写错喽！