IT日常-演算法排序(選擇排序)

前言

本文介紹了選擇排序演算法的基本邏輯與實作過程，透過範例分析陣列排序的交換步驟，以及相關的程式碼範例，幫助讀者理解選擇排序的時間與空間複雜度。選擇排序是一個簡單易懂的演算法，對於初學者來說是學習排序演算法的良好基礎。

排序演算法-選擇排序

邏輯說明:將最左邊的數與未排序中的最小數做交換

範例陣列為:524613

第一層迴圈:

從陣列的索引變數: x 為基準，用transBox儲存陣列[x]代表的值後，開始用第二層迴圈找到最小值的位置(minIdx)後做交換

第二層迴圈:

在迴圈中找到最小值的位置(minIdx)後，與transBox的位置做交換，可看以下範例了解實際交換的過程

(以C#為範例)程式碼範例:

public List<int> Sort(List<int> list)
{
	for(var x = 0; x < list.Count; x++)
	{
		var y = x+1;
		var minIdx = x;
		while (y < list.Count)
		{
			if (list[minIdx] > list[y])
			{
				minIdx = y;
			}
			y++;
		}
		var transBox = list[x];
		list[x] = list[minIdx];
		list[minIdx] = transBox;
	}
	return list;
}

結語

時間複雜度: O(n²)

空間複雜度: θ(1) (不需要額外的陣列去存資料)

參考資料

基礎演算法系列 — 你只會用 built-in function 來排序嗎

Algorithm 演算法排序筆記