function bubbleSort(arr){
constlen = arr.length
for(leti=0i arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]] // 交换位置
}
}
}returnarr}console.log(bubbleSort([3,44,15,36,26,27,2,46,4,19,50,48]))//[2,3,4,15,19,26,27,36,44,46,48,50]
链接:https://juejin.cn/post/7073640285904830471
冒泡排序的原理就是讲两个相邻的元素进行比较,数值大的元素就会往后排就是换到走遍,而我们依次比较并把大数放在后面依次循环,那么最大的元素就会排在最后边,注意:在排完一次之后最后面的数已经是最大的了所以我们并不需再再次比较最后一个元素,也就是比较的次数以此减少。
var arr=[4,2,7,2,5,8,0,4,5,7,3,8,9]
冒泡排序
i 的目的是做多少轮的 比较 j和j+1是前后数据比较
var arr=[4,1,7,2]
i==0
arr[i]=4
j=0 arr[j]=4 arr[j+1]=1 4,1,7,2---->1,4,7,2
j=1 arr[j]=4 1,4,7,2--->1,4,7,2
j=2 arr[j]=7 1,4,7,2--->1,4,2,7
### j=3 arr[j]=7 arr[j+1]不存在 因为j+1超过数组的长度,所以j必须是长度-1
i==1
j==0 arr[j]=1 1,4,2,7--->1,4,2,7
j==1 arr[j]=4 1,4,2,7--->1,2,4,7
###j==2 上面一次循环中放在最后的是最大的,所以不需要循环到2
i==2
j=0 arr[j]=1 1,2,4,7-->1,2,4,7
function sorts(arr){
var len=arr.length-1
for(var i=0i<leni++){
for(var j=0j<len-ij++){
if(arr[j]>arr[j+1]){
// if(arr[j+1]-arr[j]<0)
var temp=arr[j+1]
arr[j+1]=arr[j]
arr[j]=temp
}
}
}
}
sorts(arr)
console.log(arr)
一、 冒泡排序平均复杂度:o(n^2)空间复杂度:o(1)稳定性:稳定
步骤: 1、比较相邻的元素。如果第一个比第二个大,就交换他们两个;
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样,最后的元素应该会是最大的数;
3、针对所有的元素重复以上的步骤,除了最后一个;
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
二、选择排序
平均复杂度:o(n^2)空间复杂度:o(1)稳定性:不稳定
步骤: 1、每一次循环,找到最小的那个数,并用变量记住它的索引
2、然后将最小值放在它该在的位置上
3、持续对越来越少的元素重复上面的步骤
三、插入排序
平均复杂度:o(n^2)空间复杂度:o(1)稳定性:稳定
(1)直接插入排序:将第一个数和第二个数排序,然后构成一个有序序列;将第三个数插入进去,构成一个新的有序序列;对第四个数、第五个数......直到最后一个数,重复第二步
(2)二分插入排序:将寻找每个数插入位置的方法改为折半比较即可
四、Shell排序(插入排序的一种,又称为缩小增量排序)
平均复杂度:o(nlogn)空间复杂度:o(1)稳定性:不稳定
步骤:把数组按下标的一定增量分组,然后对每组使用直接插入排序
想学习更多前端开发的知识,就来北京尚学堂!