氣泡排序法是,從第一個元素開始,和相鄰數字比大小,若有需要就交換位置。因此也可稱為交換排序法。它的時間複雜度是 O(n^2)。
( 圖片來源 wiki )
使用哪種資料結構:Array
arr <- an unsorted array of integers
let len be the length of arr
for i (len-1 to 1) do
for j (0 to i-1) do
if (arr[j]>arr[j+1]) then
swap(arr, j, j+1)
end if
end for
end for
func swap(arr, leftIndex, rightIndex):
temp = arr[leftIndex]
arr[leftIndex] = arr[rightIndex]
arr[rightIndex] = temp
end func
debugger
function swap(arr, leftIndex, rightIndex) {
temp = arr[leftIndex]
arr[leftIndex] = arr[rightIndex]
arr[rightIndex] = temp
}
function bubbleSort(arr) {
for (let i = arr.length-1; i >= 1; i--) { // 已排序元素的控制器
console.log(i)
for (let j = 0; j <= i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j, j+1)
}
console.log(arr)
}
}
}
bubbleSort([8, 9, 2, 5, 1])