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
}

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

Comments

Software development

Data structure 資料結構

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

程式範例

Go

JavaScript

Kotlin

Python

Swift

Command Palette

Comments

Software development

Data structure 資料結構

More from this blog

程式範例

Go

JavaScript

Kotlin

Python

Swift