共计 1414 个字符，预计需要花费 4 分钟才能阅读完成。
鸡汤给大家备好了：
岁月流逝是如许残暴啊，对咱们也是如此，不要把工夫节约在不重要的人和事件上！
在计算机科学中，排序是一个经典的主题。学习排序算法的益处有三：
1. 创造性解决问题
2. 练习和坚固程序设计技能
3. 演示算法性能的极好例子
冒泡排序属于比较简单的一种排序办法。然而，很多同学到当初也不能手写一个冒泡排序。甚至通过和一些刚毕业甚至工作一两年的敌人交换后，发现他们心田对算法，抱着深深的恐怖和盲目崇拜，感觉算法如同遥不可及，只适宜那些高学历、高智商的人来学习和钻研！明天，我想把这篇献给他们，心愿他们能建立起学习的勇气和信念！
1. 什么是冒泡排序
冒泡排序算法须要遍历几次数组，在每次遍历中，比拟间断相邻的元素。如果一对元素是降序排列，则调换他们的地位，否则放弃不变。这样一来，使得较小的值像“气泡”一样，逐步浮向顶部，而较大的值沉入底部，因而称这种排序办法为冒泡排序（bubble sort）或下沉排序（sinking sort）。
第一次遍历之后，最初一个元素将成为最大的元素。第二次遍历之后，倒数第二个元素，将成为倒数第二大的元素。整个过程继续到所有的元素全副都已排好序。
2. 图解冒泡排序
通过第一次遍历后，最大的数曾经在数组开端。因为最初一个数曾经是最大数，因而不须要再思考最初一对元素。
通过第二次遍历，后两个数曾经排好序，所以只须要对除它们之外的元素进行排序。
因而，在进行第 n 次遍历时，不须要思考倒数第 n - 1 个元素，因为它们曾经排好序了！
冒泡排序伪代码：
for(int k = 1; k < list.length; k++){for(int j = 0; j < list.length-k; j++) {if(list[j] > list[j + 1]) {swap(list[i], list[i + 1]);
}
}
}3. 改良后的冒泡排序
留神到，下面的排序实际上有很屡次没有产生替换，因而，咱们能够对冒泡排序略微改良下：
boolean nextPass = true;
for(int k = 1; k < list.length && nextPass; k++){
nextPass = false;
for(int j = 0; j < list.length-k; j++) {if(list[j] > list[j + 1]) {swap(list[i], list[i + 1]);
nextPass = true;
}
}
}4. 冒泡排序工夫复杂度
最佳状况下，冒泡排序只须要一次遍历就能确定数组已排好序，不须要再进行下一次遍历。因而，最佳状况下，冒泡排序工夫复杂度为 O(n)。
最坏状况下，冒泡排序须要 次。因而比拟总次数为:
$$
(n-1) + (n-2) + (n-3) + …+ 3 + 2 + 1 = ({\frac n2^2} – {\frac n2}) = O(n^2)
$$
所以，最坏状况下，冒泡排序的工夫复杂度为:O(n^2)。
5. 附上函数
public static void bubbleSort(int[] list) {
boolean nextPass = true;
for(int k = 1; k < list.length && nextPass; k++){
nextPass = false;
for(int j = 0; j < list.length-k; j++) {if(list[j] > list[j + 1]) {int tmp = list[j];
list[j] = list[j+1];
list[j+1] = tmp;
nextPass = true;
}
}
}
}如果你感觉文章还不错，记得关注公众号：锅外的大佬
刘一手的博客
