Algorithm 演算法 - 排序系列 Selection sort 選擇排序

選擇排序是反覆進行「搜尋陣列中的最小值，將它與最左邊的元素對調」的操作。搜尋數列中的最小值使用線性搜尋。以下是圖示解釋，可以看到在每一步中我們都選擇了陣列中的最小值，然後慢慢的排序出來。

範例

數值：6 1 7 8 9 3 5 4 2

1. 利用線性搜尋找出最小值：1，然後將 1 跟最左邊的數值 6 對調 => 1 6 7 8 9 3 5 4 2
2. 從除了 1 之外剩下的數列重複第一步驟 => 1 2 7 8 9 3 5 4 6
3. 一直重複動作直到排序完成

因為搜尋的數量是 (n-1) + (n - 2) + ... 1 = (n**2) / 2，所以 Time complexity 是 O(n**2)

程式範例

Go

func selectionSort(nums []int) {
    arrLen := len(nums)

    for i := 0; i < arrLen; i++ {
        minIndex := i
        for j := i + 1; j < arrLen; j++ {
            if nums[minIndex] > nums[j] {
                minIndex := j
            }
        }

        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    }
}

JavaScript

function selectionSort(nums) {
    const arrLen = nums.length;

    for (let i = 0; i < arrLen; i++) { 
        let minIndex = i;
        for (let j = i + 1; j < arrLen; j++) { 
            if (nums[minIndex] > nums[j]) {
                minIndex = j;
            }
        }

        let temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
}

Kotlin

fun selectionSort(nums: IntArray) {
    val arrLen = nums.size
    for (i in 0..n-1) {
        var minIndex = i
        for (j in n-1 downTo i) {
            if (nums[minIndex] > nums[j]) {
                minIndex = j
            }
        }

        var temp = nums[i]
        nums[i] = nums[minIndex]
        nums[minIndex] = temp
    }
}

PHP

<?php
function selectionSort(array $nums): array
{
    $len = count($nums);

    for ($i = 0; $i < $len; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($nums[$minIndex] > $nums[$j]) {
                $minIndex = $j;
            }
        }

        $tmp = $nums[$i];
        $nums[$i] = $nums[$minIndex];
        $nums[$minIndex] = $tmp;
    }
}

Python

def selectionSort(nums -> list):
    arr_len = len(nums)

    for i in range(arr_len):
        min_index = i
        for j in range(i+1, arr_len):
            if nums[min_index] > nums[j]:
                min_index = j

        nums[i], nums[min_index] = nums[min_index], nums[i]

Rust

pub fn selection_sort(arr: &mut [i32]) {
    let len = arr.len();

    for i in 0..len {
        let mut min_index = i;
        for j in (i + 1)..len {
            if arr[min_index] > arr[j] {
                min_index = j;
            }
        }

        arr.swap(i, min_index);
    }
}

Swift

public mutating func selectionSort(nums: inout [Int]) {
    for i in 0 ..< nums.count - 1 {
        var minIndex = i

        for j in i + 1 ..< nums.count {
            if nums[j] < nums[minIndex] {
            minIndex = j
            }
        }

        swapAt(i, minIndex)
    }
}

Reference

• https://www.programiz.com/dsa/selection-sort
• https://www.geeksforgeeks.org/selection-sort/