C# 排序演算法實作：選擇排序

選擇排序是一種簡單的比較型排序演算法。其基本思想：每一趟從待排序記錄中選出關鍵字最小的記錄，順序放在已排好序的子檔案末尾，直到全部排序完畢。它屬於不穩定排序、原地排序 (空間複雜度 O(1))，時間複雜度恆為 O(n²)，不受輸入資料分布影響。

演算法步驟

1. 外層迴圈 i 從 0 到 n-2，代表當前已排序區的邊界。
2. 內層迴圈在 i+1 .. n-1 中尋找最小值索引 minIdx。
3. 將 arr[i] 與 arr[minIdx] 交換。

C# 實作程式碼

public static class SelectionSort
{
    public static void Sort(int[] arr)
    {
        for (int i = 0; i < arr.Length - 1; i++)
        {
            int minIdx = i;
            for (int j = i + 1; j < arr.Length; j++)
                if (arr[j] < arr[minIdx]) minIdx = j;

            if (minIdx != i)
            {
                int tmp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = tmp;
            }
        }
    }
}

// 測試
static void Main()
{
    int[] data = { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
    SelectionSort.Sort(data);
    Console.WriteLine("選擇排序結果：" + string.Join(", ", data));
}

複雜度分析

優缺點總結

• 優點：實作簡單、交換次數少 (適合寫入成本高的儲存體)、空間效率佳。
• 缺點：時間複雜度固定 O(n²)、不穩定、無法提前終止 (不像氣泡排序可加旗標)。

何時使用？

僅適合教學示範或極小資料量 (n < 20) 且記憶體極度受限、寫入操作極其昂貴的特殊場景。生產環境請使用 Array.Sort / List<T>.Sort。