( )17.請問以下排序演算法，其時間複雜度、空間複雜度及穩定性(Stability)的敘述何者正確?
(A) Qucik Sort 及 Merge Sort 的時間複雜度均為 O(nlogn)，空間複雜度均為 O(logn)。
(B) Heap Sort 的時間複雜度為 O(nlogn) ，空間複雜度為 O(1)，且為非穩定(not stable)演算法。
(C) Selection Sort 的時間複雜度為 O(n2 ) ，且為穩定(stable)演算法。
(D) Bubble Sort 的時間複雜度為 O(n2 ) ，且為非穩定(not stable)演算法。

在開始之前，先解釋一下幾個概念：

• 時間複雜度 (Time Complexity)：衡量演算法執行時間與輸入資料量 n 之間的關係。
• 空間複雜度 (Space Complexity)：衡量演算法執行所需額外記憶體空間與輸入資料量 n 之間的關係。
• 穩定性 (Stability)：指如果排序資料中有兩個或多個具有相同鍵值的元素，排序後這些相同鍵值的元素的相對順序是否保持不變。如果保持不變，則是穩定排序；反之則是不穩定排序。

A) Quick Sort 及 Merge Sort 的時間複雜度均為 O(nlogn)，空間複雜度均為 O(logn)。

• Quick Sort (快速排序)

  • 時間複雜度： 平均情況下為 O(nlogn)，最壞情況下為 O(n2)（例如，輸入資料已經完全有序或逆序）。
  • 空間複雜度： 平均情況下為 O(logn)（遞迴呼叫堆疊的深度），最壞情況下為 O(n)。
  • 穩定性： 不穩定。因為它會交換不相鄰的元素，可能會改變相同鍵值元素的相對順序。

• Merge Sort (合併排序)

  • 時間複雜度： 最好、平均、最壞情況下均為 O(nlogn)。
  • 空間複雜度： O(n)。因為合併排序需要一個額外的空間來儲存合併後的子陣列。
  • 穩定性： 穩定。在合併過程中，可以確保相同鍵值元素的相對順序不變。

• 判斷 (A)：

  • 時間複雜度方面，Quick Sort 最壞情況不是 O(nlogn)，且 Merge Sort 總是 O(nlogn)。
  • 空間複雜度方面，Merge Sort 是 O(n) 而不是 O(logn)。
  • 因此，(A) 敘述是錯誤的。

B) Heap Sort 的時間複雜度為 O(nlogn) ，空間複雜度為 O(1)，且為非穩定(not stable)演算法。

• Heap Sort (堆積排序)

  • 時間複雜度： 最好、平均、最壞情況下均為 O(nlogn)。這是因為建構堆和從堆中提取元素的過程都是 O(logn)，總共執行 n 次。
  • 空間複雜度： O(1)。它是一個原地 (in-place) 排序演算法，只需要常數額外空間來儲存臨時變數。
  • 穩定性： 不穩定。在調整堆的過程中，父節點和子節點的交換可能會改變相同鍵值元素的相對順序。

• 判斷 (B)：

  • 時間複雜度 O(nlogn) 正確。
  • 空間複雜度 O(1) 正確。
  • 非穩定演算法也正確。
  • 因此，(B) 敘述是正確的。

C) Selection Sort 的時間複雜度為 O(n^2) ，且為穩定(stable)演算法。

• Selection Sort (選擇排序)

  • 時間複雜度： 最好、平均、最壞情況下均為 O(n2)。因為它總是需要 n−1 趟，每趟找到最小（或最大）元素並放到正確的位置。
  • 空間複雜度： O(1)。
  • 穩定性： 不穩定。因為它會將找到的最小（或最大）元素與當前位置的元素進行交換。這個交換可能會破壞相同鍵值元素的相對順序。
    • 例如：[5a, 8, 5b, 2]。第一趟找到 2，將 2 與 5a 交換，變成 [2, 8, 5b, 5a]。此時 5a 和 5b 的相對順序改變了。

• 判斷 (C)：

  • 時間複雜度 O(n2) 正確。
  • 但它是一個不穩定演算法。
  • 因此，(C) 敘述是錯誤的。

D) Bubble Sort 的時間複雜度為 O(n^2) ，且為非穩定(not stable)演算法。

• Bubble Sort (泡沫排序)

  • 時間複雜度： 最好情況下為 O(n)（如果陣列已經有序），平均和最壞情況下為 O(n2)。
  • 空間複雜度： O(1)。
  • 穩定性： 穩定。因為它只會交換相鄰的元素。如果兩個元素的值相同，它不會交換它們，從而保持了它們的相對順序。

• 判斷 (D)：

  • 時間複雜度 O(n2) 在最壞和平均情況下是正確的。
  • 但它是一個穩定演算法。
  • 因此，(D) 敘述是錯誤的。

最終結論：

根據上述分析，只有選項 (B) 的敘述是完全正確的。

The final answer is B​

17. 排序演算法的時間複雜度、空間複雜度及穩定性敘述

正確的敘述是 (B) Heap Sort 的時間複雜度為 O(nlogn)，空間複雜度為 O(1)，且為非穩定 (not stable) 演算法。

讓我們逐一分析每個選項：

• (A) Quick Sort 及 Merge Sort 的時間複雜度均為 O(nlogn)，空間複雜度均為 O(logn)。

  • Quick Sort (快速排序)：
    • 時間複雜度： 平均情況為 O(nlogn)，最壞情況為 O(n2)。
    • 空間複雜度： 遞迴調用棧空間，平均情況為 O(logn)，最壞情況為 O(n)。
  • Merge Sort (合併排序)：
    • 時間複雜度： 始終為 O(nlogn)。
    • 空間複雜度： 需要額外的空間來儲存合併後的子陣列，為 O(n)。
  • 結論： 此選項不正確，因為 Merge Sort 的空間複雜度是 O(n)，而非 O(logn)。

• (B) Heap Sort (堆積排序) 的時間複雜度為 O(nlogn)，空間複雜度為 O(1)，且為非穩定 (not stable) 演算法。

  • 時間複雜度： 始終為 O(nlogn)。
  • 空間複雜度： 堆積排序是一種原地 (in-place) 排序演算法，除了少量的臨時變數外，不需要額外的空間，因此空間複雜度為 O(1)。
  • 穩定性 (Stability)： 堆積排序是非穩定排序演算法。因為在構建堆積的過程中或在從堆頂移除元素並重新調整堆積時，可能會改變相同值元素的相對順序。
  • 結論： 此選項是正確的。

• (C) Selection Sort (選擇排序) 的時間複雜度為 O(n^2)，且為穩定 (stable) 演算法。

  • 時間複雜度： 始終為 O(n2)。
  • 穩定性 (Stability)： 選擇排序是非穩定排序演算法。在每次迭代中，它會找到未排序部分的最小元素並將其與當前位置的元素交換。如果當前位置的元素與未排序部分中的另一個相同值的元素交換，則會破壞相同值元素的相對順序。
  • 結論： 此選項不正確，因為選擇排序是非穩定演算法。

• (D) Bubble Sort (氣泡排序) 的時間複雜度為 O(n^2)，且為非穩定 (not stable) 演算法。

  • 時間複雜度： 始終為 O(n2)。
  • 穩定性 (Stability)： 氣泡排序是穩定的排序演算法。它只會在相鄰元素逆序時進行交換，並且如果兩個相鄰元素相等，它們的相對位置不會改變。
  • 結論： 此選項不正確，因為氣泡排序是穩定演算法。