上节介绍了桶排序，虽然说他很快，但是也有一个弊端，如果我们的数值范围很大，比如我们数值的范围是0~2亿，我们就需要2亿+1个桶，就算只有五个数要排序，我们也要准备那么多桶，这个空间消耗太吓人了。还有一个情况是如果我们的数值有小数，这个桶该怎么解决？这也很难。
下面我们就来看一个新的算法——冒泡排序。
冒泡排序的主要思路就是每次都比较相邻的两个元素，根据大小交换位置。
例如我们要把12、35、99、18、76这5个数从大到小进行排序，那么我们就要把越小的数越放到后面。冒泡排序的思想就是每次遍历未排序的序列，把最小的移动到最后或最前（在这里从大到小，就是把最小的移到最后）。
首先比较前两个数，发现12比35小，就交换位置。序列就变成了35、12、99、18、76，下面在比较第二和第三个数，发现12比99小，于是也交换位置。序列变成了35、99、12、18、76，一次列推，最终序列会变成35、99、18、76、12 。现在最小的一个数12已经移动到了最后。
我们现在可以准备排序前四个数了，第五个数已经排序完成了。
还是按照上面的方法，排序后的序列编程35、99、76、18、 (12)。
这样在排序前三个，一层一层的排序，就好像最小的一个一个冒泡的最后面一样，所以叫冒泡排序。这里总共有N个数，实际上就需要重复上述操作N-1次。这个算法让我想起了拍集体照的时候小个儿总是一个一个的被往后推，是不是就是受了这个影响发明的算法。
最后看一下时间复杂度，实际上这个算法是个双重循环，所以它的时间复杂度是O(N²) 。这个时间复杂度很高，冒泡排序在1956年开始就有人开始研究，后续也有很多人对这个算法进行改进，但结果都很惨，1974年图灵奖获得者所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”
本文原创与本人博客，更多请访问 http://irfen.me
©原创文章，转载请注明来源： 赵伊凡's Blog
©本文链接地址: 跟我学算法（二）——咕嘟咕嘟的冒泡排序
“跟我学算法（二）——咕嘟咕嘟的冒泡排序”的37个回复