選擇排序(Selection Sort)

介紹

選擇排序是反覆進行搜尋數列中最小值並與最左邊的數值對調，選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多(n-1)次交換，比較次數第一回合(n-1)次，第二回合(n-2)次….到第n-1回合一次，因此是 (n-1) + (n-1) + ... + 1 ≈ n^2/2，時間複雜度跟泡沫排序一樣是O(n^2)。

(圖片來源)

虛擬碼

function selection_sort (array) {
    for(i from 0 to array.length-2){
        var minIndex = i;
        for(j from i to array.length-1){
            if array[j] < array[minIndex]:
                minIndex = j
        }
        swap(array[minIndex], array[i])
    }

    return array
}

複雜度

時間複雜度

無論資料順序如何，都會執行兩個迴圈

$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 - 2; i++){
        let minIndex = i
        for(let j = i; j <= nums.length - 1; j++){
            if (nums[j] < nums[minIndex]){
                minIndex = j
            }
        }
        // swap nums[minIndex] and nums[i]
        [nums[minIndex], nums[i]] = [nums[i], nums[minIndex]]
    }
    return nums
};