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

五大排序演算法

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;
        Swap(arr, i, min);
    }
}

2. 氣泡排序

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

3. 快速排序

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

4. 插入排序

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

5. 希爾排序

public void Sort(int[] arr) {
    int inc = 1;
    while (inc <= arr.Length / 9) inc = 3 * inc + 1;
    for (; inc > 0; inc /= 3)
        for (int i = inc; i < arr.Length; i++) {
            int temp = arr[i], j = i;
            while (j >= inc && arr[j-inc] > temp) { arr[j] = arr[j-inc]; j -= inc; }
            arr[j] = temp;
        }
}

測試資料

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

所有演算法均可正確排序上述資料。