選擇排序法(Selection Sort)
簡介
選擇排序法(Selection Sort)是排序演算法的一種,也是一種簡單容易理解的演算法,其概念是反覆從未排序的數列中取出最小的元素,加入到另一個的數列,結果即為已排序的數列。運算流程如下:
- 從未排序的數列中找到最小的元素。
- 將此元素取出並加入到已排序數列最後。
- 重複以上動作直到未排序數列全部處理完成。
流程示意圖:
然而實作上通常不使用額外的數列來儲存已排序的部分,而使用原地(In-place)的方式來完成,數列的左半部表示已排序部分,右半部表示未排序部分,不另外使用數列。從未排序部分找到最小的元素,利用交換的方式將元素放置已排序部分的尾端。運算流程如下:
- 從未排序的數列中找到最小的元素。
- 將此元素與已排序部分的尾端元素進行交換。
- 重複以上動作直到未排序數列全部處理完成。
流程示意圖:
選擇排序法的比較複雜度固定式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
#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
#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
下載