#define MAXSIZE    10
typedef struct {
    int r[MAXSIZE + 1];
    int length;
} SqList;

void swap(SqList *L, int i, int j) {
    int tmp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = tmp;
}

• 氣泡排序法(Bubble Sort)

// 只是交換排序
void BubbleSort0(SqList *L) {
    int i, j;
    for (i = 1; i <= L->length; i++) {
        for (j = i + 1; j <= L->length; j++) {
            if (L->r[i] > L->r[j])
                swap(L, i, j);
        }
    }
}

void BubbleSort(SqList *L) {
    int i, j;
    for (i = 1; i <= L->length; i++) {
        // 由後往前
        for (j = L->length - 1; j >= i; j--) {
            if (L->r[j] > L->r[j + 1])
                swap(L, j, j + 1);
        }
    }
}

void BubbleSort2(SqList *L) {
    int i, j;
    Status flag = TRUE;
    for (i = 1; i <= L->length && flag; i++) {
        flag = FALSE;
        for (j = L->length - 1; j >= i; j--) {
            if (L->r[j] > L->r[j + 1]) {
                swap(L, j, j + 1);
                flag = TRUE;
            }
        }
    }
}

• 最壞時間複雜度O(n^2)
• 最優時間複雜度O(n)
• 平均時間複雜度O(n^2)

• 空間複雜度O(n)，輔助空間O(1)

• 簡單選擇排序法(Simple Selection Sort)

void SelectSort(SqList *L) {
    int i, j, min;
    for (i = 1; i < L->length; i++) {
        min = i;
        for (j = i + 1; j < L-length; j++) {
            if (L=>r[min] > L->r[j])
                min = j;
        }
        if (i != min)
            swap(L, i, min);
    }
}

• 最壞時間複雜度O(n^2)
• 最優時間複雜度O(n^2)
• 平均時間複雜度O(n^2)

• 空間複雜度O(n)，輔助空間O(1)

• 直接插入排序法(Straight Insertion Sort)

void InsertSort(SqList *L) {
    int i, j;
    for (i = 2; i <= L->length; i++) {
        if (L->r[i] < L->r[i- 1]) {
            L->r[0] = L->r[i];
            for (j = i - 1; L->r[j] > L->r[0]; j--)
                L->r[j + 1] = L->r[j];
            L->r[j + 1] = L->r[0];
        }
    }
}

• 最壞時間複雜度O(n^2)
• 最優時間複雜度O(n)
• 平均時間複雜度O(n^2)

• 空間複雜度O(n)，輔助空間O(1)

• Shell排序法(Shell Sort)

void ShellSort(SqList *L) {
    int i, j;
    int inc = L->length;
    do {
        inc = inc / 3 + 1;
        for (i = inc + 1; i <= L->length; i++) {
            if (L->r[i] < L->r[i - inc]) {
                L->r[0] = L->r[i];
                for (k = i - inc; j > 0 && L->r[0] < L->r[j]; j -= inc)
                    L->r[j + inc] = L->r[j];
                L->r[j + inc] = L->r[0];
            }
        }
    } while(inc > 1);
}

增量序列的最後一個增量值必須等於1

• 最壞時間複雜度O(n^(3/2)) O(nlog2(n))
• 最優時間複雜度O(n)
• 平均時間複雜度O(n^2)

• 空間複雜度O(n)

• 堆積排序法(Heap Sort)

堆積是一種具有下列性質的完整二元樹

• 每個節點的值都大(小)於或等於其左右孩子節點的值，稱為最大(小)堆積

P427

• 合併排序法

123

• 快速排序法

123