[Algorithm] Bubble Sort (泡沫排序)
Bubble Sort 的定義 (參考維基百科)
重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來
走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成
主要步驟
- 比較相鄰的元素。如果第一個比第二個大，就將他們兩個交換位置
- 向每一對相鄰元素作同樣操作，從開始第一對到結尾最後一對
時間複雜度：O(N^2)
範例程式碼
Ruby 範例
附上 Ruby 的 online sandbox，有興趣可以把 code 貼進去玩玩看
arr = [1, 4, 2, 3, 5, 7, 8, 6, 9]
def bubble_sort(array)
array_length = array.size
return array if array_length <= 1
swapped = true
while swapped do
swapped = false
(array_length - 1).times do |i|
if array[i] > array[i + 1]
array[i], array[i + 1] = array[i + 1], array[i]
swapped = true
end
end
end
array
end
pp bubble_sort(arr)
結果如下
JavaScript 範例
JavaScript 的 online sandbox，有興趣可以把 code 貼進去玩玩看
const arr = [1, 4, 2, 3, 5, 7, 8, 6, 9]
function bubbleSort (array) {
const arrayLength = array.length;
for (let i = 0; i < arrayLength; i++) {
for (let j = 0; j < arrayLength; j++) {
if(array[j] > array[j+1]) {
let temp = array[j]
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array
}
console.log(bubbleSort(arr))
結果如下
