題組內容
六、請以時間效能為考量根據,從下列幾種不同的排序法(sorting)中,選擇適合各小
題情況的排序法。(每小題 4 分,共 20 分)
快速排序法(Quick Sort)、插入排序法(Insertion Sort)、合併排序法(Merge Sort)
、氣泡排序法(Bubble Sort)、堆積排序法(Heap Sort)
⑴擬排序的對象大部分都已依需要的關係排列(例如由小到大)。
詳解 (共 2 筆)
詳解
插入排序法(Insertion Sort)
原因:
插入排序法在處理大部分已經排好序的數列時表現非常優秀。它的時間複雜度在最好的情況下為 O(n),因為它只需要遍歷數列並檢查每個元素是否在正確的位置。如果數列已經幾乎排好序,插入排序所需的操作次數非常少,因此在這種情況下是最佳選擇。
其餘題目的選擇:
⑵ 擬排序的對象完全是隨機排列的
快速排序法(Quick Sort)
原因:
快速排序法在平均情況下具有 O(nlogn)的時間複雜度,並且其常數因子相對較小,通常在實際應用中非常快。對於隨機排列的數列,快速排序法的性能非常優異。
⑶ 擬排序的對象數目非常龐大,且排序過程需要較多的額外記憶體
合併排序法(Merge Sort)
原因:
合併排序法在最壞情況下具有 O(nlogn)的時間複雜度,並且其穩定性和分治策略使其非常適合處理非常龐大的數列。然而,需要注意的是,合併排序法的空間複雜度為 O(n),這可能會增加額外的記憶體需求。
⑷ 擬排序的對象數目非常龐大,且排序過程中希望儘量減少額外的記憶體使用量
堆積排序法(Heap Sort)
原因:
堆積排序法的時間複雜度為 O(nlogn),並且其空間複雜度為 O(1)(除了需要輸入數列之外),因此在需要儘量減少額外記憶體使用的情況下,堆積排序法是一個很好的選擇。
⑸ 擬排序的對象數目較小(例如少於 100 個)
插入排序法(Insertion Sort)
原因:
插入排序法對於小數量的數列非常高效,因為其簡單性和較小的常數因子使其在這種情況下表現良好。即使在最壞情況下,插入排序法的時間複雜度為 O(n平方),但由於數列較小,實際運行時間仍然很快。
詳解
幾乎已排好的狀況適用插入排序法和氣泡排序法。