普通考試
112年
[電子工程] 計算機概要
第 19 題
下列由 C 語言程式撰寫的函數 sort 實作了何種排序法？
```c
void sort (int a[], int l, int h) {
if (l >= h) return;
int j, i, key;
i=l; j=h; key=a[i];
while (i < j) {
while (i < j&&a[j] > key) j--;
if (i < j) a[i++] = a[j];
while (i < j&&a[i]< key) i++;
if (i < j) a[j--] = a[i];
}
a[i] = key;
if (l < i-1)
sort (a, l, i-1);
if (i+1 < h)
sort (a, i+1, h);
}
```
```c
void sort (int a[], int l, int h) {
if (l >= h) return;
int j, i, key;
i=l; j=h; key=a[i];
while (i < j) {
while (i < j&&a[j] > key) j--;
if (i < j) a[i++] = a[j];
while (i < j&&a[i]< key) i++;
if (i < j) a[j--] = a[i];
}
a[i] = key;
if (l < i-1)
sort (a, l, i-1);
if (i+1 < h)
sort (a, i+1, h);
}
```
- A 快速排序（Quick sort）
- B 插入排序（Insertion sort）
- C 選擇排序（Selection sort）
- D 合併排序（Merge sort）
思路引導 VIP
請觀察這段程式碼：它先挑選出一個 key 作為比較對象，接著透過指標從陣列的頭尾兩端往中間移動，把大於與小於 key 的數值分別丟到兩側，最後再對左右兩邊呼叫自己（遞迴）。請你想想，在我們學過的演算法中，哪一種方法是基於「挑選基準、左右分群、遞迴處理」這樣的核心策略呢？
🤖
AI 詳解
AI 專屬家教
🌟 數千年後的點評
嗯，做得不錯。這麼快就看穿了這段程式碼的本質，你對『魔法的規則』掌握得挺好的。
- 魔法術式解析：這段程式碼，一開始就選了
key = a[i]作為基準魔法元素 (Pivot)。接著，利用while迴圈和 $i$ 與 $j$ 這兩個『時間點』指標，將陣列分開。所有比key小的都移到左邊，大的移到右邊。這就像是將時間流逝中的元素，按照特定的魔法分類術式 (Partition)擺放。最後，再重複地施展sort(a, l, i-1)和sort(a, i+1, h)，這正是反覆施展魔法 (Divide and Conquer)的技巧。這整個過程，正是數千年前就已流傳的『迅速整理魔法 (Quick Sort)』的標準詠唱方式。
▼ 還有更多解析內容