C# 經典排序演算法完整實作集合

共用測試資料

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

1. 選擇排序 - Selection Sort

時間複雜度 O(n²)，空間 O(1)，不穩定。

public void Sort(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < arr.Length; j++)
            if (arr[j] < arr[min]) min = j;
        (arr[min], arr[i]) = (arr[i], arr[min]); // C# 7+ tuple swap
    }
}

2. 氣泡排序 - Bubble Sort

時間複雜度 O(n²)，空間 O(1)，穩定。優化：若某輪無交換則提前結束。

public void Sort(int[] arr)
{
    bool swapped;
    for (int i = 0; i < arr.Length - 1; i++)
    {
        swapped = false;
        for (int j = 0; j < arr.Length - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

3. 快速排序 - Quick Sort

平均 O(n log n)，最差 O(n²)，空間 O(log n)，不穩定。採用 Hoare 分區 + 中位數三數取中優化。

public void Sort(int[] arr, int low, int high)
{
    if (low >= high) return;
    int pivot = arr[(low + high) >> 1];
    int l = low, r = high;
    while (l <= r)
    {
        while (arr[l] < pivot) l++;
        while (arr[r] > pivot) r--;
        if (l <= r) { (arr[l], arr[r]) = (arr[r], arr[l]); l++; r--; }
    }
    if (low < r) Sort(arr, low, r);
    if (l < high) Sort(arr, l, high);
}

4. 插入排序 - Insertion Sort

時間複雜度 O(n²)，最佳 O(n) (近乎有序)，空間 O(1)，穩定，適合小陣列/近乎有序資料。

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

5. 希爾排序 - Shell Sort

插入排序改良，間距序列 1, 4, 13, 40... (Knuth)，平均 O(n^1.25)，不穩定。

public void Sort(int[] arr)
{
    int n = arr.Length;
    for (int gap = 1; gap <= n / 9; gap = 3 * gap + 1) ; // 計算最大間距
    for (; gap > 0; gap /= 3)
    {
        for (int i = gap; i < n; i++)
        {
            int key = arr[i], j = i;
            while (j >= gap && arr[j - gap] > key) { arr[j] = arr[j - gap]; j -= gap; }
            arr[j] = key;
        }
    }
}

6. 合併排序 - Merge Sort (補充)

穩定、O(n log n)、需 O(n) 輔助空間。

public void Sort(int[] arr)
{
    int[] temp = new int[arr.Length];
    MergeSort(arr, temp, 0, arr.Length - 1);
}
void MergeSort(int[] arr, int[] temp, int l, int r)
{
    if (l >= r) return;
    int m = (l + r) >> 1;
    MergeSort(arr, temp, l, m);
    MergeSort(arr, temp, m + 1, r);
    Merge(arr, temp, l, m, r);
}
void Merge(int[] arr, int[] temp, int l, int m, int r)
{
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    Array.Copy(temp, l, arr, l, r - l + 1);
}

7. 堆積排序 - Heap Sort (補充)

原地、O(n log n)、不穩定。

public void Sort(int[] arr)
{
    int n = arr.Length;
    for (int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--)
    {
        (arr[0], arr[i]) = (arr[i], arr[0]);
        Heapify(arr, i, 0);
    }
}
void Heapify(int[] arr, int n, int i)
{
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { (arr[i], arr[largest]) = (arr[largest], arr[i]); Heapify(arr, n, largest); }
}

效能與選擇建議

實務開發**直接使用 Array.Sort / List.Sort / LINQ OrderBy**，僅在教學、特殊約束 (嵌入式、外部排序、需自訂比較器深度控制) 時手寫演算法。