本文转载自微信公众号《JS每日一问》，作者慧慧。转载本文请联系JS每日一问公众号.1、什么是冒泡排序（BubbleSort），是计算机科学领域比较简单的排序算法？冒泡排序的思想是像碳酸饮料中的二氧化碳气泡最终会浮到最上面一样，让一个数据元素（即排列好的数据）漂浮起来，因此得名“冒泡排序”如果我们要排序12、35、99、18、76这五个数字从大到小，那么数字越大越需要放在前面。18然后比较76和99，发现76比99小，所以不用调换顺序。然后比较99和35，发现99大于35，交换顺序再比较99和12，发现99大于12，交换顺序最后在第一遍排序结果变成99、12,35,76,18，如下图所示：从上图可以看出，第一次排序后，可以得到最大的元素，然后第二次排序对剩下的4个元素进行排序，如图下图中：第二次排序后结果为99,76,12,35,18然后开始第三次排序结果为99,76,35,12,18然后第四次排序结果为99、76、35、18、12，经过4次排序，只需要排序一个12。此时，没有可比较的元素。这个时候排序就完成了。2.如何实现如果要实现从小到大的排序，算法原理如下：先比较相邻的元素，如果第一个元素大于第二个元素，则交换它们，对每一对做同样的工作相邻元素的，从最开始的第一对到最后的最后一对，这样最后一个元素会是最大的数，对除最后一个以外的所有元素重复以上步骤，对每个越来越少的元素重复以上步骤timeuntiltherearenopairofnumberstocompare用代码表示如下：functionbubbleSort(arr){constlen=arr.length;for(leti=0;iarr[j+1]){//相邻元素两两比较vartemp=arr[j+1];//元素交换arr[j+1]=arr[j];arr[j]=temp;}}}returnarr;}可以看到：每轮排序都在冒泡排序它会一次做一个元素，即最后需要进行n-1轮排序，并且在每一轮排序中，需要比较相邻的两个元素。在最坏的情况下，每次比较之后，都会有交换位置的必要。此时时间复杂度为O(n^2)优化。冒泡排序常用的改进方法是增加一个符号变量交换，用于标记某次排序过程中是否有数据交换。如果某个排序过程中没有数据交换，说明数据已经按要求排列好，可以立即结束排序，避免不必要的比较。可以设置一个符号变量pos来记录每次排序中最后一次交换的位置，由于pos位置之后的记录已经交换到位，所以在进行下一次排序时扫描到pos位置即可，如下：functionbubbleSort1(arr){consti=arr.length-1;//开始时，最后一个位置保持不变while(i>0){letpos=0;//每次行程开始时，没有记录交换为(letj=0;jarr[j+1]){lettmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;pos=j;//记录最后一次交换的位置}}i=pos;//为下一次排序做准备}returnarr;}在待排序序列有序的情况下，只进行一轮需要分拣，不需要交换。这时候的情况是最好的，时间复杂度是O(n)并且从上面的比较可以看出，只有后一个元素比前一个元素大（小）时，他们才会交换位置弹出。对于相同大小的元素，不需要交换位置，所以对于相同大小的元素，相对位置是不会改变的，因此，冒泡排序是稳定的3.应用场景冒泡排序的核心部分是double嵌套循环，时间复杂度为O(N2)，时间复杂度相对较高，一般不推荐，因为冒泡排序比较简单，一般用来给入门的同学介绍算法的概念编程参考https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306https://www.runoob.com/w3cnote/bubble-sort.htmlhttp://data.biancheng.net/view/116.htmlhttps://dsb123dsb.github.io/2017/03/07/js%E5%AE%9E%E7%8E%B0%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E4%BB%A5%E5%8F%8A%E4%BC%98%E5%8C%96/
