Algorithm 演算法 - 排序系列 Bubble sort 氣泡排序

Bubble sort 其原理是反覆的進行「由右至左，相鄰的值兩兩比較後重新排序」。因其向水中泡泡浮起的樣子，所以以此得名。 其複雜度是，第一回執行 n-1、第二回執行 n-2 依序到第 n-1 回執行 1 次。 (n-1) + (n-2) + ... + 1 = n^2 / 2。 時間複雜度：O(n^2)

程式範例

Go

func bubbleSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        for j := 0; j < length - 1 - i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

JavaScript

function bubbleSort(arr) {
    const 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]) {           // 相鄰元素兩兩比較
                const temp = arr[j + 1];   // 元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

Kotlin

fun bubbleSort(arr: IntArray) {
    for (i in 0 until (numbers.size - 1)) {
        for (j in 0 until (arr.size - i - 1)) {
            if (arr[j] > arr[j + 1]) {
                val tmp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = tmp
            }
        }
    }
}

Python

def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Swift

func bubbleSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else {return arr}
    for i in 0..<arr.count {
        for j in 0..<arr.count-i-1 {
            if arr[j]>arr[j + 1] {
                arr.swapAt(j + 1, j)
            }
        }
    }

    return arr
}