冒泡排序:顾名思义就是气泡从水中向外冒越来越大
基本思想:从左到右每次比较两个相邻的数,大的往后移动,小的往前移动,这里有个易误点,每次向右移动的过程中都是较大的数参与后续比较,最终的结果是得到最大的数排在最后面,要有逆向思维,他其实是从大到小排的,只不过将大数放在后面。
示例:例如一个数组[3,6,7,4,5],首先3和6比较,位置不变,然后右移一位,6和7比较仍然不变,再右移,7和4比较,7比4大,交换位置,再后移一位,7和5比较(前面一步7的位置后移一位了),7比5大,交换位置,第一轮循环下来,得到的数组排序是[3,6,4,5,7],第二轮时仍然从左到右,只是没有必要比较最后一个数了,因为它是最大的肯定不用交换位置,依次下去就得到第二大,第三大...
代码如下:
function bubleSort (arr){
for(let i=0;i<arr.length-1;i++){ //第一层遍历是计次,一共需要遍历n-1论,和以往的遍历计点不同
for(let j=0;j<arr.length-1-i;j++){ //第二层遍历计点,每次往后移动一位,每增加一轮,就少比较一个已经排好序的数
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
}
}
}
return arr
}
注解以上是为了便于理解创造的术语,并非官方术语,计次和计点是我的理解意思,计次表示循环是次数的累加,计点是数据的位置后移,获取新的数据
网友评论