49. 下列哪一種排序法所需的儲存空間最多？
(A) Bubble sort
(B) Insertion sort
(C) Quick sort
(D) Selection sort

在排序演算法中，所需的儲存空間通常指的是額外空間複雜度（Auxiliary Space Complexity），也就是除了儲存原始資料所需的空間之外，演算法執行時額外需要的記憶體空間。

讓我們分析各個排序演算法的空間複雜度：

• (A) 氣泡排序（Bubble Sort）：

  • 這是一種原地（in-place）排序演算法。它只需要一個額外的臨時變數來進行元素交換。
  • 空間複雜度：O(1)（常數空間）。

• (B) 插入排序（Insertion Sort）：

  • 這也是一種原地（in-place）排序演算法。它只需要一個額外的臨時變數來儲存當前要插入的元素。
  • 空間複雜度：O(1)（常數空間）。

• (C) 快速排序（Quick Sort）：

  • 快速排序通常是遞迴實現的。雖然它被認為是一種原地排序演算法（不使用額外的陣列來儲存排序結果），但其遞迴呼叫會使用呼叫堆疊（call stack）。
  • 在平均情況下，遞迴深度是 O(logn)，所以空間複雜度是 O(logn)。
  • 在最壞情況下（例如，當陣列已經排序或反向排序，且沒有使用好的樞紐選擇策略時），遞迴深度可以達到 O(n)，此時空間複雜度是 O(n)。
  • 相較於其他原地排序演算法，快速排序的遞迴堆疊空間需求是其主要額外空間消耗。

• (D) 選擇排序（Selection Sort）：

  • 這也是一種原地（in-place）排序演算法。它只需要一個額外的臨時變數來進行元素交換。
  • 空間複雜度：O(1)（常數空間）。

結論： 綜合來看，氣泡排序、插入排序和選擇排序的空間複雜度都是 O(1)。而快速排序由於其遞迴特性，在最壞情況下需要 O(n) 的堆疊空間，在平均情況下需要 O(logn) 的堆疊空間。

因此，在這些選項中，快速排序所需的儲存空間最多（特別是在考慮遞迴堆疊時）。

The final answer is C​

​在所列的排序算法中，快速排序（Quick Sort）通常需要比冒泡排序（Bubble Sort）、插入排序（Insertion Sort）和選擇排序（Selection Sort）更多的儲存空間。​這是因為快速排序在實現時，常使用遞迴方式進行分割，會在呼叫堆疊中佔用額外的空間。​在最壞情況下，遞迴深度可能達到 O(n)，導致較高的空間複雜度。​Medium+1Medium+1

相比之下，冒泡排序、插入排序和選擇排序的空間複雜度為 O(1)，因為它們只需要少量的額外儲存空間來交換元素。​

因此，正確答案是 (C) Quick sort。