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

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

### 程式範例

#### Go

```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

```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

```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

```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

```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
}
```