快速排序核心邏輯
- 選基準（樞軸），將陣列分為「小於基準」與「大於基準」兩部分。
- 遞歸處理左右子陣列，直到區間長度 ≤ 1。
代碼實現（教科書標準寫法）
typedef struct { int key; } RecordType;
typedef struct { RecordType r[MAXSIZE]; int length; } SqlList;
void QuickSort(SqlList *L, int low, int high) {
if (low < high) {
int pivot = Partition(L, low, high);
QuickSort(L, low, pivot - 1);
QuickSort(L, pivot + 1, high);
}
}
int Partition(SqlList *L, int low, int high) {
RecordType pivot = L->r[low]; // 以第一個元素為樞軸
while (low < high) {
while (low < high && L->r[high].key >= pivot.key) high--;
L->r[low] = L->r[high];
while (low < high && L->r[low].key <= pivot.key) low++;
L->r[high] = L->r[low];
}
L->r[low] = pivot;
return low;
}
關鍵點解析
L->r[0] 常作暫存單元（哨兵），避免邊界檢查。- 雙向掃描：
high 向左找 < pivot，low 向右找 > pivot，交換。
- 平均時間複雜度 O(n log n)，最壞 O(n²)（有序陣列），可用「三數取中」或隨機樞軸優化。
測試主程式
int main() {
SqlList L = { .length = 8 };
int data[] = {49, 38, 65, 97, 76, 13, 27, 49};
for (int i = 0; i < 8; i++) L.r[i+1].key = data[i]; // r[1..n]
QuickSort(&L, 1, 8);
for (int i = 1; i <= 8; i++) printf("%d ", L.r[i].key);
return 0;
}
