算法原理:
????1.比較相鄰的元素柴我。如果第一個比第二個大解寝,就交換他們兩個。
????2.對每一對相鄰元素作同樣的工作艘儒,從開始第一對到結(jié)尾的最后一對聋伦。在這一點(diǎn),最后的元素應(yīng)該會是最大的數(shù)界睁。
????3.針對所有的元素重復(fù)以上的步驟觉增,除了最后一個。
????4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟翻斟,直到?jīng)]有任何一對數(shù)字需要比較逾礁。
時間復(fù)雜度:
????冒泡排序的最壞時間復(fù)雜度為O(n2)
????平均時間復(fù)雜度為O(n2)
算法穩(wěn)定性:
????冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較访惜,交換也發(fā)生在這兩個元素之間嘹履。所以腻扇,如果兩個元素相等,我想你是不會再無聊地把他們倆交換一下的砾嫉;如果兩個相等的元素沒有相鄰幼苛,那么即使通過前面的兩兩交換把兩個相鄰起來,這時候也不會交換焕刮,所以相同元素的前后順序并沒有改變蚓峦,所以冒泡排序是一種穩(wěn)定排序算法。
JavaScript:
let arrSort = [8, 6, 1, 2, 5, 3, 7, 4, 5]
function bubbleSort(arr){?
?let j = arr.length, change, n=0?
?while(j>0)
{
?????for(let i =0; i<j-1;i++)
????{
? ? ? if(arr[i]>arr[i+1]){
? ? ? ? change = arr[i+1]
? ? ? ? arr[i+1] = arr[i]
? ? ? ? arr[i] = change
? ? ? }
? ? ? n++
? ? }
? ? j--;
? }
? return {arr, n}
}
const res = bubbleSort(arrSort)