---
tags: 演算法, LeetCode
disqus: HackMD
---

# 氣泡排序(Bubble Sort)

## 介紹

氣泡排序是反覆進行將**相鄰數字做比較後重新排序**，因排序時一個一個浮出序列頂部，很像水中泡泡浮起來的樣子，亦稱泡泡排序，最壞情況下，數是由大排到小，每次比較後將數值對調，因此，時間複雜度為`O(n^2)`。

[圖片來源](https://raywenderlich.github.io/swift-algorithm-club/Bubble%20Sort/)

## 虛擬碼

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

## 複雜度

### 時間複雜度

$O(n^2)$

### 空間複雜度

$O(1)$

## 實戰

[75. Sort Colors](https://leetcode.com/problems/sort-colors/)

### 題目說明

給定一個數組 `nums`，其中有 `n` 個對象，顏色為紅色、白色或藍色，並對它們進行排序，顏色按紅色、白色和藍色的順序排列。 將使用整數 0、1 和 2 分別表示紅色、白色和藍色。 必須在不使用`library`的排序功能的情況下解決此問題。


### 解法

使用泡泡排序解決此問題。

將陣列內數值由左至右雙雙比較，假設左邊數值大於右邊數值則互換位置，跑完一輪迴圈最右邊數值一定是最大的，進行第二圈比較時就可以省略比較最後一個數字，第三圈就忽略最後兩個數字，依此類推。

**Javascript**

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    for (let i=0; i < nums.length - 1; i++){
        for (let j=0; j < nums.length - 1 - i; j++){
            if (nums[j] > nums[j+1]) {
                [nums[j], nums[j+1]] = [nums[j+1], nums[j]]
            }
        }
    }
    return nums;
};

> [name=@joe94113] [time=Tue, Oct 25, 2022 10:00 PM] [color=#907bf7]