- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
冒泡排序，简单粗暴，一句话解释:
冒泡排序在每次冒泡操作时会比较相邻的两个元素，看是否满足大小关系要求，不满足就将它俩互换。一直迭代到不再需要交换，也就是排序完成。
constbubbleSort=function(arr){constlen=arr.lengthif(len<2)returnarrfor(leti=0;i<len;i++){for(letj=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){consttemp=arr[j]arr[j]=arr[j+1]arr[j+1]=temp}}}returnarr}
- 时间复杂度: O(n^2)
- 空间复杂度: O(1)
- 稳定
注意：这里的稳定是指，冒泡排序是稳定的排序算法。
什么是稳定的排序算法呢？
排序算法的稳定性
仅仅用执行效率和内存消耗来判断排序算法的优劣是不够的，针对排序算法，还有一个重要的度量指标，稳定性。
意思是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
举个🌰：
比如我们有一组数据：1，9，2，5，8，9。按照大小排序之后就是 1，2，5，8，9，9。
这组数据中有两个 9，经过某种排序算法排序后，如果两个 9 的前后顺序没有改变，我们就把这种排序算法称为稳定的排序算法。
否则，就是不稳定的排序算法。
冒泡排序优化
上面的代码还可以进行优化，当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不需要再继续执行后续的冒泡操作了。
constbubbleSort=function(arr){constlen=arr.lengthletflag=falseif(len<2)returnarrfor(leti=0;i<len;i++){flag=false// 提前退出冒泡循环的标志for(letj=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){consttemp=arr[j]arr[j]=arr[j+1]arr[j+1]=tempflag=true// 表示有数据交换}}if(!flag)break// 没有数据交换，提前退出}returnarr}
Metadata
Metadata
Assignees
Labels
No labels