演算法 - 選擇排序法 (Selection Sort)

簡介

選擇排序法 (Selection Sort) 是排序演算法的一種，也是一種簡單容易理解的演算法，其概念是反覆從未排序的數列中取出最小的元素，加入到另一個的數列，結果即為已排序的數列。運算流程如下：

1. 從未排序的數列中找到最小的元素。
2. 將此元素取出並加入到已排序數列最後。
3. 重複以上動作直到未排序數列全部處理完成。

流程示意圖：

然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地 (In-place) 的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。從未排序部分找到最小的元素，利用交換的方式將元素放置已排序部分的尾端。運算流程如下：

1. 從未排序的數列中找到最小的元素。
2. 將此元素與已排序部分的尾端元素進行交換。
3. 重複以上動作直到未排序數列全部處理完成。

流程示意圖：

選擇排序法的比較複雜度固定是 O(n^2)，不過交換次數則是 O(n)，在最佳情況可以到 O(0)，比起氣泡排序法的比較次數少很多，所以效能上會比較好。

分析

• 最佳時間複雜度：O(n^2)
• 平均時間複雜度：O(n^2)
• 最差時間複雜度：O(n^2)
• 空間複雜度：O(1)
• Stable sort：是

虛擬碼

額外空間版本

function sort(list)
	var sorted = []
	while list.length > 0
		min = 取出 list 中最小元素
		sorted.add(min)
	end while
	list = sorted
end function

In-place

function sort(list)
	for i = 0; i < list.length - 1; ++i
		minIndex = i;
		for j = i + 1; j < list.length; ++j
			if list[j] < list[minIndex]
				minIndex = j;
			end if
		end for
		if minIndex != i
			swap(list[minIndex], list[i]);
		end if
	end for
end function

語法

C#

額外空間版本 (物件導向寫法)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SelectionSort
{
    class ExtraSpace
    {
        public static void Sort(int[] array)
        {
            List<int> sorted = new List<int>(array.Length);
            List<int> unsorted = array.ToList();
            while (unsorted.Count > 0)
            {
                int n = ExtractMin(unsorted);
                sorted.Add(n);
            }
            sorted.ToArray().CopyTo(array, 0);
        }

        private static int ExtractMin(List<int> unsorted)
        {
            int index = 0, min = unsorted[0];
            for (int i = 0; i < unsorted.Count; ++i)
            {
                if (unsorted[i] < min)
                {
                    index = i;
                    min = unsorted[i];
                }
            }
            unsorted.RemoveAt(index);
            return min;
        }
    }
}

In-place

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SelectionSort
{
    class InPlace
    {
        public static void Sort(int[] array)
        {
            for (int i = 0, minIndex; i < array.Length - 1; ++i)
            {
                minIndex = i;
                for (int j = i + 1; j < array.Length; ++j)
                    if (array[j] < array[minIndex])
                        minIndex = j;
                if (minIndex != i)
                    Swap(array, minIndex, i);
            }
        }

        private static void Swap(int[] array, int indexA, int indexB)
        {
            int tmp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = tmp;
        }
    }
}

Java

額外空間版本 (物件導向寫法)

import java.util.ArrayList;
import java.util.List;


public class ExtraSpace {
    public static void Sort(int[] array)
    {
        List<Integer> sorted = new ArrayList<Integer>(array.length);
        List<Integer> unsorted = new ArrayList<Integer>(array.length);
        for (int n : array)
            unsorted.add(n);
        while (unsorted.size() > 0)
        {
            Integer n = ExtractMin(unsorted);
            sorted.add(n);
        }
        for (int i = 0;i < array.length;++i)
            array[i] = sorted.get(i);
    }

    private static Integer ExtractMin(List<Integer> unsorted)
    {
        int index = 0, min = unsorted.get(0);
        for (int i = 0; i < unsorted.size(); ++i)
        {
            if (unsorted.get(i) < min)
            {
                index = i;
                min = unsorted.get(i);
            }
        }
        unsorted.remove(index);
        return min;
    }
}

In-place

public class InPlace {
    public static void Sort(int[] array)
    {
        for (int i = 0, minIndex; i < array.length - 1; ++i)
        {
            minIndex = i;
            for (int j = i + 1; j < array.length; ++j)
                if (array[j] < array[minIndex])
                    minIndex = j;
            if (minIndex != i)
                Swap(array, minIndex, i);
        }
    }

    private static void Swap(int[] array, int indexA, int indexB)
    {
        int tmp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = tmp;
    }
}

C++

額外空間版本 (物件導向寫法)

ExtraSpace.h

#ifndef EXTRASPACE_H
#define EXTRASPACE_H

#include <vector>
#include <memory.h>

using namespace std;

class ExtraSpace
{
    public:
        static void Sort(int* array, int length);
    protected:
    private:
        static int ExtractMin(vector<int>& unsorted);
};

#endif // EXTRASPACE_H
ExtraSpace.cpp
```C++
#include "ExtraSpace.h"

void ExtraSpace::Sort(int* array, int length)
{
    vector<int> sorted;
    vector<int> unsorted(length);
    for(int i = 0; i < length; i++)
        unsorted[i] = array[i];
    while (unsorted.size() > 0)
    {
        int n = ExtraSpace::ExtractMin(unsorted);
        sorted.push_back(n);
    }
    memcpy(array, &sorted[0], sizeof( int ) * sorted.size());
}

int ExtraSpace::ExtractMin(vector<int>& unsorted)
{
    int index = 0, min = unsorted[0];
    for (int i = 0; i < unsorted.size(); ++i)
    {
        if (unsorted[i] < min)
        {
            index = i;
            min = unsorted[i];
        }
    }
    unsorted.erase(unsorted.begin() + index);
    return min;
}

#### In-place
InPlace.h
```C++
#ifndef INPLACE_H
#define INPLACE_H

#include <algorithm>

using namespace std;

class InPlace
{
    public:
        static void Sort(int* array, int length);
    protected:
    private:
};

#endif // INPLACE_H

InPlace.cpp

#include "InPlace.h"

void InPlace::Sort(int* array, int length)
{
    for (int i = 0, minIndex; i < length - 1; ++i)
    {
        minIndex = i;
        for (int j = i + 1; j < length; ++j)
            if (array[j] < array[minIndex])
                minIndex = j;
        if (minIndex != i)
            swap(array[minIndex], array[i]);
    }
}

隨機產生 20000 筆資料實測

C#
InPlace: 1237ms
ExtraSpace: 2232ms

Java
InPlace: 270ms
ExtraSpace: 621ms

C++
InPlace: 910ms
ExtraSpace: 2120ms

延伸閱讀

排序演算法 (Sorting)