JavaScript 冒泡算法是一種非常常見的排序算法,在不同領域都有廣泛應用,比如在前端開發中,對表格進行排序、在后端對數據進行排序等。
冒泡排序算法的核心思想是比較相鄰元素的大小,如果左邊的元素大于右邊的元素,則交換它們的位置,反之則不改變。每次比較都會把最大的值冒泡到最后,所以稱為冒泡排序。
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i< len - 1; i++) {
for (let j = 0; j< len - 1 - i; j++) {
if (arr[j] >arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
假設現有一個數組 [5, 3, 8, 6, 4] 需要進行排序,那么第一次循環會比較 5 和 3 的大小,發現 5 大于 3,所以需要交換它們的位置,得到 [3, 5, 8, 6, 4]。接著比較 5 和 8 的大小,不需要交換位置,得到 [3, 5, 8, 6, 4]。再比較 8 和 6,需要交換位置,得到 [3, 5, 6, 8, 4]。依次比較 8 和 4,需要交換位置,得到 [3, 5, 6, 4, 8]。第一次循環結束,8 已經冒泡到最后一個位置了。
接著第二次循環開始,因為 8 已經在它應該在的位置,所以只需要比較前面四個元素的大小。第二次循環完畢后,7 再次冒泡到了它應該在的位置,直到排序完成。
總的來說,冒泡排序算法最好情況下的時間復雜度為 O(n),最壞情況下為 O(n2)。也就是說,當數組已經按照從小到大的順序排好了時,算法只需要比較一遍,就可以把排序完成。但是如果數組亂序,每個元素需要比較多次,時間效率就會變低。
在實際使用中,冒泡排序算法的效率并不高,一般情況下更多使用插入排序、快速排序等算法。