C# 經典排序演算法實作：氣泡、選擇、插入、希爾排序

四種基本排序演算法 C# 實作

本文提供氣泡排序、選擇排序、插入排序、希爾排序的完整 C# 程式碼，附帶測試主程式，適合演算法教學與面試複習。

1. 氣泡排序

public class BubbleSorter
{
    public void Sort(int[] list)
    {
        bool swapped;
        for (int i = 1; i < list.Length; i++)
        {
            swapped = false;
            for (int j = 0; j < list.Length - i; j++)
            {
                if (list[j] > list[j + 1])
                {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // 提早結束優化
        }
    }
}

2. 選擇排序

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

            int temp = list[minIdx];
            list[minIdx] = list[i];
            list[i] = temp;
        }
    }
}

3. 插入排序

public class InsertionSorter
{
    public void Sort(int[] list)
    {
        for (int i = 1; i < list.Length; i++)
        {
            int key = list[i];
            int j = i - 1;
            while (j >= 0 && list[j] > key)
            {
                list[j + 1] = list[j];
                j--;
            }
            list[j + 1] = key;
        }
    }
}

4. 希爾排序

public class ShellSorter
{
    public void Sort(int[] list)
    {
        int n = list.Length;
        // 計算初始間距 (Knuth 序列: 1, 4, 13, 40...)
        int gap = 1;
        while (gap <= n / 3) gap = 3 * gap + 1;

        for (; gap > 0; gap /= 3)
        {
            for (int i = gap; i < n; i++)
            {
                int temp = list[i];
                int j = i;
                while (j >= gap && list[j - gap] > temp)
                {
                    list[j] = list[j - gap];
                    j -= gap;
                }
                list[j] = temp;
            }
        }
    }
}

測試程式

int[] data = { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };

new BubbleSorter().Sort(data);
Console.WriteLine("Bubble: " + string.Join(", ", data));

data = new[] { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
new SelectionSorter().Sort(data);
Console.WriteLine("Selection: " + string.Join(", ", data));

data = new[] { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
new InsertionSorter().Sort(data);
Console.WriteLine("Insertion: " + string.Join(", ", data));

data = new[] { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
new ShellSorter().Sort(data);
Console.WriteLine("Shell: " + string.Join(", ", data));

複雜度比較

實務建議： 實際專案請直接使用 Array.Sort 或 List<T>.Sort（內建 Introspective Sort，效能最佳）。