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

# 選擇排序(Selection Sort)

## 介紹

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

([圖片來源](http://www.xybernetics.com/techtalk/SortingAlgorithmsExplained/SortingAlgorithmsExplained.html))

## 虛擬碼

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](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 - 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
};

> [name=@joe94113] [time=Wed, Oct 26, 2022 04:00 PM] [color=#907bf7]