氣泡排序(Bubble Sort)

介紹

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

圖片來源

虛擬碼

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

題目說明

給定一個數組 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;
};

@joe94113Tue, Oct 25, 2022 10:00 PM